We propose a cooperative motion and task planning scheme for multi-agent systems where the agents have independently assigned local tasks, specified as linear temporal logic formulas. These tasks contain hard and soft sub-specifications. A least-violating initial plan is synthesized first for the potentially infeasible task and the partially-known workspace. This discrete plan is then implemented by the potential-field-based navigation controllers. While the system runs, each agent updates its knowledge about the workspace via its sensing capability and shares this knowledge with its neighbouring agents. Based on the knowledge update, each agent verifies and revises its motion plan in real time. It is ensured that the hard specification is always fulfilled for safety and the satisfaction for the soft specification is improved gradually. The design is distributed as only local interactions are assumed. The overall framework is demonstrated by a case study and an experiment.
BaierCKatoenJ-P (2008) Principles of model checking. Cambridge, MA: The MIT Press.
2.
BeltaCBicchiAEgerstedtMFrazzoliEKlavinsEPappasGJ (2007) Symbolic planning and control of robot motion. IEEE Robotics and Automation Magazine14: 61–71.
3.
BeltaCIslerVPappasGJ (2005) Discrete abstractions for robot motion planning and control in polygonal environments. IEEE Transactions on Robotics21(5): 864–874.
4.
BhatiaAKavrakiLEVardiMY (2010) Sampling-based motion planning with temporal goals. In: IEEE international conference on robotics and automation (ICRA), Anchorage, AK.
5.
BhatiaAMalyMRKavrakiLEVardiMY (2011) Motion planning with complex goals. IEEE Robotics and Automation Magazine18(3): 55–64.
6.
BoydSVandenbergheL (2009) Convex Optimization. Cambridge: Cambridge University Press.
7.
ChanEPFYangY (2009) Shortest path tree computation in dynamic graphs. IEEE Transactions on Computers58(4): 541–557.
8.
ChenYXuCDStefanescuABeltaC (2012) Formal approach to the deployment of distributed robotic teams. IEEE Transactions on Robotics28(1): 158–171.
9.
ClarkeEMGrumbergOPeledDA (1999) Model Checking. Cambridge, MA: The MIT Press.
10.
DesaiJOstrowskiJKumarV (1998) Controlling formations of multiple mobile robots. In: IEEE international conference on robotics and automation (ICRA), pp. 2864–2869.
11.
DimarogonasDVKyriakopoulosKJ (2007) Decentralized navigation functions for multiple robotic agents with limited sensing capabilities. Journal of Intelligent and Robotic Systems48(3): 411–433.
FainekosGEGirardAKress-GazitHPappasGJ (2009) Temporal logic motion planning for dynamic mobile robots. Automatica45(2): 343–352.
14.
FainekosGELoizouSGPappasGJ (2006) Translating temporal logic to controller specifications. In: IEEE conference on decision and control (CDC), San Diego, CA.
15.
FilippidisIFDimarogonasDVKyriakopoulosKJ (2012) Decentralized multi-agent control from local LTL specifications. In: IEEE conference on decision and control (CDC), Maui, HI.
16.
ForneyGJr (1966) Generalized minimum distance decoding. IEEE Transactions on Information Theory12(2): 125–131.
17.
GastinPOddouxD (2001) Fast LTL to Büchi automaton translation. In: International conference on computer aided verification (CAV’01), Paris, France.
18.
GuoMJohanssonKHDimarogonasDV (2013) Revising motion planning under linear temporal logic specifications in partially known workspaces. In: IEEE international conference on robotics and automation (ICRA), Karlsruhe, Germany.
19.
GuoMDimarogonasDV (2013) Reconfiguration in motion planning of single- and multi-agent systems under infeasible local LTL specifications. In: IEEE conference on decision and control (CDC), Florence, Italy.
20.
GuoMDimarogonasDV (2014) Distributed plan reconfiguration via knowledge transfer in multi-agent systems under local LTL specifications. In: IEEE international conference on robotics and automation (ICRA), Hongkong, China.
21.
HeemelsWPMHJohanssonKHTabuadaP (2012) An introduction to event-triggered and self-triggered control. In: IEEE conference on decision and control (CDC), Maui, HI.
22.
JohnsonBKress-GazitH (2011) Probabilistic analysis of correctness of high-Level robot behavior with sensor error. In: Proceedings of robotics: science and systems, Los Angeles, CA.
23.
KaramanSFrazzoliE (2008) Vehicle routing with linear temporal logic specifications: applications to multi-UAV mission planning. In: Navigation, and control conference in AIAA Guidance, Minnesota, MN.
24.
KaramanSFrazzoliE (2011) Sampling-based algorithms for optimal motion planning. The International Journal of Robotics Research30(7): 846–894.
25.
KimKFainekosGESankaranarayananS (2012) On the revision problem of specification automaton. In: IEEE international conference on robotics and automation (ICRA), pp. 5171–5176.
26.
KloetzerMBeltaC (2010) Automatic deployment of distributed teams of robots from temporal logic specifications. IEEE Transactions on Robotics26(1): 48–61.
27.
KloetzerMDingXCBeltaC (2011) Multi-robot deployment from LTL specifications with reduced communication. In: IEEE conference on decision and control (CDC), Florida, FL.
28.
KoditschekDERimonE (1990) Robot navigation functions on manifolds with boundary. Advances in Applied Mathematics11: 412–442.
29.
Kress-GazitHWongpiromsarnTTopcuU (2011) Correct, reactive robot control from abstraction and temporal logic specifications. IEEE Robotics and Automation Magazine18(3): 65–74.
30.
LaValleSM (2006) Planning Algorithms. Cambridge: Cambridge University Press.
31.
LindemannSRHusseinIILaValleSM (2006) Real time feedback control for nonholonomic mobile robots with obstacles. In: IEEE conference on decision and control (CDC), San Diego, CA.
32.
LivingstonSCMurrayRMBurdickJW (2012) Backtracking temporal logic synthesis for uncertain environments. In: IEEE international conference on robotics and automation (ICRA), Minnesota, MN.
33.
LoizouSGJadbabaieA (2006) Density functions for navigation function based systems. In: IEEE conference on decision and control (CDC), San Diego, CA.
34.
LoizouSGKyriakopoulosKJ (2003) Closed loop navigation for multiple non-holonomic vehicles. In: IEEE international conference on robotics and automation, vol. 3, pp. 4240–4245.
35.
LoizouSGKyriakopoulosKJ (2004) Automatic synthesis of multi-agent motion tasks based on LTL specifications. In: IEEE conference on decision and control (CDC), Paradise Island, Bahamas.
36.
MalyMRLahijanianMKavrakiLEKress-GazitHVardiMY (2013) Iterative temporal motion planning for hybrid systems in partially unknown environments. In: Proceedings of the 16th international conference on hybrid systems: computation and control. New York: ACM Press, pp. 353–362.
37.
MisraSOommenBJ (2005) Dynamic algorithms for the shortest path routing problem: learning automata-based solutions. IEEE Transactions on Systems and Cybernetics35(6): 1179–1192.
38.
OikonomopoulosASLoizouSGKyriakopoulosKJ (2009) Coordination of multiple non-holonomic agents with input constraints. In: IEEE international conference on robotics and automation (ICRA), Kobe, Japan.
39.
RamanVKress-GazitH (2011) Analyzing unsynthesizable specifications for high-Level robot behavior. In: Proceedings of computer aided verification, Snowbird, UT.
40.
SmithSLTumovaJBeltaCRusD (2011) Optimal path planning for surveillance with temporal logic constraints. The International Journal of Robotics Research30(14): 1695–1708.
41.
TopcuUOzayNLiuJMurrayRM (2012) On synthesizing robust discrete controllers under modeling uncertainty. In: Hybrid system: computation and control, Beijing, China, pp. 85–94.
42.
TumovaJDimarogonasDV (2014) A receding horizon approach to multi-agent planning from local LTL specifications. In: American control conference (ACC), Portland, OR.
43.
TumovaJHallGCKaramanSFrazzoliERusD (2013) Least-violating control strategy synthesis with safety rules. In: Proceedings of the 16th international conference on hybrid systems: computation and control. New York: ACM Press.
44.
UlusoyASmithSLDingXCBeltaCRusD (2013) Optimality and robustness in multi-Robot path planning with temporal logic constraints. The International Journal of Robotics Research32(8): 889–911.
45.
WolffETopcuUMurrayRM (2012) Robust control of uncertain markov decision processes with temporal logic specifications. In: IEEE conference on decision and control (CDC), Maui, HI.
