More Web Proxy on the site http://driver.im/

survey

Multiple Mobile Robot Task and Motion Planning: A Survey

Authors:

Luke Antonyshyn,

Jefferson Silveira,

Joshua MarshallAuthors Info & Claims

ACM Computing Surveys, Volume 55, Issue 10

Article No.: 213, Pages 1 - 35

https://doi.org/10.1145/3564696

Published: 02 February 2023 Publication History

Abstract

With recent advances in mobile robotics, autonomous systems, and artificial intelligence, there is a growing expectation that robots are able to solve complex problems. Many of these problems require multiple robots working cooperatively in a multi-robot system. Complex tasks may also include the interconnection of task-level specifications with robot motion-level constraints. Many recent works in the literature use multiple mobile robots to solve these complex tasks by integrating task and motion planning. We survey recent contributions to the field of combined task and motion planning for multiple mobile robots by categorizing works based on their underlying problem representations, and we identify possible directions for future research. We propose a taxonomy for task and motion planning based on system capabilities, applicable to multi-robot and single-robot systems.

References

[1]

Ahmed M. Afifi, Omar H. Alhosainy, Catherine M. Elias, Omar M. Shehata, and Elsayed I. Morgan. 2019. Deep policy-gradient based path planning and reinforcement cooperative q-learning behavior of multi-vehicle systems. In IEEE International Conference on Vehicular Electronics and Safety (ICVES). IEEE, 1–7.

Digital Library

[2]

Aliakbar Akbari, Muhayyuddin, and Jan Rosell. 2019. Knowledge-oriented task and motion planning for multiple mobile robots. J. Experim. Theoret. Artif. Intell. 31, 1 (2019), 137–162.

[3]

Javier Alonso-Mora, Jonathan A. DeCastro, Vasumathi Raman, Daniela Rus, and Hadas Kress-Gazit. 2018. Reactive mission and motion planning with deadlock resolution avoiding dynamic obstacles. Auton. Robots 42, 4 (2018), 801–824.

Digital Library

[4]

Barbara Arbanas Ferreira, Antun Ivanovic, Marko Car, Matko Orsag, Tamara Petrovic, and Stjepan Bogdan. 2018. Decentralized planning and control for UAV–UGV cooperative teams. Auton. Robots 42 (122018).

[5]

Gürdal Arslan, Jason R. Marden, and Jeff S. Shamma. 2007. Autonomous vehicle-target assignment: A game-theoretical formulation. J. Dynam. Syst., Meas., Contr. 129, 5 (2007), 584–596.

[6]

Xiaoshan Bai, Weisheng Yan, Ming Cao, and Dong Xue. 2019. Distributed multi-vehicle task assignment in a time-invariant drift field with obstacles. IET Contr. Theor. Applic. 13, 17 (2019), 2886–2893.

[7]

Christopher Banks, Sean Wilson, Samuel Coogan, and Magnus Egerstedt. 2020. Multi-agent task allocation using cross-entropy temporal logic optimization. In IEEE International Conference on Robotics and Automation (ICRA). IEEE, 7712–7718.

[8]

Sarah Barlow, Youngjun Choi, Simon Briceno, and Dimitri N. Mavris. 2019. A multi-UAS trajectory optimization methodology for complex enclosed environments. In International Conference on Unmanned Aircraft Systems (ICUAS). IEEE, 596–604.

[9]

Michael Beetz, Raja Chatila, Joachim Hertzberg, and Federico Pecora. 2016. AI reasoning methods for robotics. In Springer Handbook of Robotics. Springer, 329–356.

[10]

Tolga Bektas. 2006. The multiple traveling salesman problem: An overview of formulations and solution procedures. Omega 34, 3 (2006), 209–219.

[11]

Calin Belta, Antonio Bicchi, Magnus Egerstedt, Emilio Frazzoli, Eric Klavins, and George J. Pappas. 2007. Symbolic planning and control of robot motion (grand challenges of robotics). IEEE Robot. Autom. Mag. 14, 1 (2007), 61–70.

[12]

Ulrich Berger. 2007. Brown’s original fictitious play. J. Econ. Theor. 135, 1 (2007), 572–578.

[13]

Dimitri P. Bertsekas. 1988. The auction algorithm: A distributed relaxation method for the assignment problem. Annals Oper. Res. 14, 1 (1988), 105–123.

Digital Library

[14]

Sumana Biswas, Sreenatha G. Anavatti, and Matthew A. Garratt. 2017. Nearest neighbour based task allocation with multi-agent path planning in dynamic environments. In International Conference on Advanced Mechatronics, Intelligent Manufacture, and Industrial Automation (ICAMIMIA). IEEE, 181–186.

[15]

Lawrence E. Blume. 1993. The statistical mechanics of strategic interaction. Games Econ. Behav. 5, 3 (1993), 387–424.

[16]

Francesco Bullo, Emilio Frazzoli, Marco Pavone, Ketan Savla, and Stephen L. Smith. 2011. Dynamic vehicle routing for robotic systems. Proc. IEEE 99, 9 (2011), 1482–1504.

[17]

Flavia Causa, Giancarmine Fasano, and Michele Grassi. 2018. Multi-UAV path planning for autonomous missions in mixed GNSS coverage scenarios. Sensors 18, 12 (2018), 4188.

[18]

Mingzhi Chen and Daqi Zhu. 2018. A workload balanced algorithm for task assignment and path planning of inhomogeneous autonomous underwater vehicle system. IEEE Trans. Cog. Devel. Syst. 11, 4 (2018), 483–493.

[19]

Yaojie Chen, Shanshan Xiang, and Feixiang Chen. 2019. Research on a task planning method for multi-ship cooperative driving. J. Shang. Jiaot. Univ. (Sci.) 24, 2 (2019), 233–242.

[20]

Rafael Rodrigues da Silva, Vince Kurtz, and Hai Lin. 2019. Active perception and control from temporal logic specifications. IEEE Contr. Syst. Lett. 3, 4 (2019), 1068–1073.

[21]

Torbjørn S Dahl, Maja Matarić, and Gaurav S Sukhatme. 2009. Multi-robot task allocation through vacancy chain scheduling. Robot. Auton. Syst. 57, 6-7 (2009), 674–687.

Digital Library

[22]

Jin Dai, Alessandro Benini, Hai Lin, Panos J. Antsaklis, Matthew J. Rutherford, and Kimon P. Valavanis. 2016. Learning-based formal synthesis of cooperative multi-agent systems with an application to robotic coordination. In 24th Mediterranean Conference on Control and Automation (MED). IEEE, 1008–1013.

[23]

Neil T. Dantam. 2020. Task and Motion Planning. Springer Berlin, 1–9. DOI:

[24]

Rachael N. Darmanin and Marvin K. Bugeja. 2017. A review on multi-robot systems categorised by application domain. In 25th Mediterranean Conference on Control and Automation (MED). IEEE, 701–706.

[25]

João Paulo Lima Silva de Almeida, Renan Taizo Nakashima, Flávio Neves-Jr, and Lúcia Valéria Ramos de Arruda. 2019. Bio-inspired on-line path planner for cooperative exploration of unknown environment by a multi-robot system. Robot. Auton. Syst. 112 (2019), 32–48.

[26]

Rina Dechter, Itay Meiri, and Judea Pearl. 1991. Temporal constraint networks. Artif. Intell. 49, 1–3 (1991), 61–95.

Digital Library

[27]

Ziquan Deng and Zhaodan Kong. 2020. Multi-agent cooperative pursuit-defense strategy against one single attacker. IEEE Robot. Autom. Lett. 5, 4 (2020), 5772–5778.

[28]

Edsger W. Dijkstra et al. 1959. A note on two problems in connexion with graphs. Numerische Mathematik 1, 1 (1959), 269–271.

Digital Library

[29]

Emrah Dönmez and Adnan Fatih Kocamaz. 2018. Multi target task distribution and path planning for multi-agents. In International Conference on Artificial Intelligence and Data Processing (IDAP). IEEE, 1–7.

[30]

Sérgio Ronaldo Barros dos Santos, Cairo Lúcio Nascimento Júnior, and Sidney N. Givigi. 2014. Planning and learning for cooperative construction task with quadrotors. In IEEE International Systems Conference Proceedings. IEEE, 57–64.

[31]

Sérgio Ronaldo Barros dos Santos, Cairo Lúcio Nascimento Júnior, and Sidney N. Givigi. 2014. Planning and learning for cooperative construction task with quadrotors. In IEEE International Systems Conference Proceedings. IEEE, 57–64.

[32]

Xiaojun Duan, Huiying Liu, Hong Tang, Qing Cai, Fan Zhang, and Xiaotian Han. 2020. A novel hybrid auction algorithm for multi-UAVs dynamic task assignment. IEEE Access 8 (2020), 86207–86222.

[33]

Mattia D’Emidio and Imran Khan. 2019. Collision-free allocation of temporally constrained tasks in multi-robot systems. Robot. Auton. Syst. 119 (2019), 151–172.

Digital Library

[34]

Stefan Edelkamp, Morteza Lahijanian, Daniele Magazzeni, and Erion Plaku. 2018. Integrating temporal reasoning and sampling-based motion planning for multigoal problems with dynamics and time windows. Robot. Autom. Lett. 3, 4 (2018), 3473–3480.

[35]

Orel Elimelech, Roni Stern, Meir Kalech, and Yedidya Bar-Zeev. 2017. Diagnosing resource usage failures in multi-agent systems. Expert Syst. Appl. 77, C (July2017), 44–56. DOI:

Digital Library

[36]

Eloy Garcia, David W. Casbeer, and Meir Pachter. 2019. Optimal strategies of the differential game in a circular region. IEEE Contr. Syst. Lett. 4, 2 (2019), 492–497.

[37]

Eloy Garcia, David W. Casbeer, Alexander Von Moll, and Meir Pachter. 2020. Multiple pursuer multiple evader differential games. IEEE Trans. Automat. Control 66, 5 (2020), 2345–2350.

[38]

Caelan Reed Garrett, Rohan Chitnis, Rachel Holladay, Beomjoon Kim, Tom Silver, Leslie Pack Kaelbling, and Tomás Lozano-Pérez. 2021. Integrated task and motion planning. Ann. Rev. Contr., Robot. Auton. Syst. 4 (2021), 265–293.

[39]

Caelan Reed Garrett, Tomas Lozano-Perez, and Leslie Pack Kaelbling. 2018. FFRob: Leveraging symbolic planning for efficient task and motion planning. Int. J. Robot. Res. 37, 1 (2018), 104–136.

Digital Library

[40]

R. Gayathri and V. Uma. 2018. Ontology based knowledge representation technique, domain modeling languages and planners for robotic path planning: A survey. ICT Express 4, 2 (2018), 69–74.

[41]

Brian P. Gerkey and Maja J. Matarić. 2004. A formal analysis and taxonomy of task allocation in multi-robot systems. Int. J. Robot. Res. 23, 9 (2004), 939–954.

[42]

Rob Gerth, Doron Peled, Moshe Y. Vardi, and Pierre Wolper. 1995. Simple on-the-fly automatic verification of linear temporal logic. In International Conference on Protocol Specification, Testing and Verification. Springer, 3–18.

[43]

M. Ghallab, D. Nau, and P. Traverso. 2004. Automated Planning: Theory and Practice. Elsevier Science. 2003064381

Digital Library

[44]

Oussama Ghdiri, Wael Jaafar, Safwan Alfattani, Jihene Ben Abderrazak, and Halim Yanikomeroglu. 2020. Energy-efficient multi-UAV data collection for IoT networks with time deadlines. In IEEE Global Communications Conference. IEEE, 1–6.

Digital Library

[45]

David González, Joshué Pérez, Vicente Milanés, and Fawzi Nashashibi. 2015. A review of motion planning techniques for automated vehicles. IEEE Trans. Intell. Transport. Syst. 17, 4 (2015), 1135–1145.

Digital Library

[46]

Héctor H. González-Baños, David Hsu, and Jean-Claude Latombe. 2018. Motion planning: Recent developments. Auton. Mob. Robots (2018), 373–416.

[47]

Meng Guo, Sofie Andersson, and Dimos V. Dimarogonas. 2018. Human-in-the-loop mixed-initiative control under temporal tasks. In IEEE International Conference on Robotics and Automation (ICRA). IEEE, 6395–6400.

Digital Library

[48]

Meng Guo and Dimos V. Dimarogonas. 2016. Task and motion coordination for heterogeneous multiagent systems with loosely coupled local tasks. IEEE Trans. Automat. Sci. Eng. 14, 2 (2016), 797–808.

[49]

Eric A. Hansen and Shlomo Zilberstein. 2001. LAO*: A heuristic search algorithm that finds solutions with loops. Artif. Intell. 129, 1 (2001), 35–62.

Digital Library

[50]

Peter E. Hart, Nils J. Nilsson, and Bertram Raphael. 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern. 4, 2 (1968), 100–107.

[51]

Patrik Haslum, Nir Lipovetzky, Daniele Magazzeni, and Christian Muise. 2019. An introduction to the planning domain definition language. Synth. Lect. Artif. Intell. Mach. Learn. 13, 2 (2019), 1–187.

[52]

Wolfgang Hönig. 2018. Scalable task and motion planning for multi-robot systems in obstacle-rich environments. In 17th International Conference on Autonomous Agents and MultiAgent Systems. 1746–1751.

Digital Library

[53]

Wolfgang Hönig, T. K. Satish Kumar, Liron Cohen, Hang Ma, Hong Xu, Nora Ayanian, and Sven Koenig. 2017. Summary: Multi-agent path finding with kinematic constraints. In 26th International Joint Conference on Artificial Intelligence. 4869–4873.

[54]

Hanqiao Huang and Tao Zhuo. 2019. Multi-model cooperative task assignment and path planning of multiple UCAV formation. Multim. Tools Applic. 78 (012019).

Digital Library

[55]

Rufus Isaacs. 1999. Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization. Dover Publications.

[56]

Richard C. Jeffrey and John P. Burgess. 2006. Formal Logic: Its Scope and Limits. Hackett Publishing.

[57]

In-Bae Jeong, Woo-Ri Ko, Gyeong-Moon Park, Deok-Hwa Kim, Yong-Ho Yoo, and Jong-Hwan Kim. 2017. Task intelligence of robots: Neural model-based mechanism of thought and online motion planning. IEEE Trans. Emerg. Topics Computat. Intell. 1, 1 (2017), 41–50.

[58]

Xiao Jia and Max Q.-H. Meng. 2013. A survey and analysis of task allocation algorithms in multi-robot systems. In IEEE International Conference on Robotics and Biomimetics (ROBIO). IEEE, 2280–2285.

[59]

Liwei Jiang, Felipe Gonzalez, and Aaron McFadyen. 2020. Cooperative game theory based multi-UAV consensus-based formation control. In International Conference on Unmanned Aircraft Systems (ICUAS). 93–99.

[60]

Yuqian Jiang, Fangkai Yang, Shiqi Zhang, and Peter Stone. 2019. Task-motion planning with reinforcement learning for adaptable mobile service robots. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 7529–7534.

Digital Library

[61]

Ariyan M. Kabir, Shantanu Thakar, Prahar M. Bhatt, Rishi K. Malhan, Pradeep Rajendran, Brual C. Shah, and Satyandra K. Gupta. 2020. Incorporating motion planning feasibility considerations during task-agent assignment to perform complex tasks using mobile manipulators. In IEEE International Conference on Robotics and Automation (ICRA). IEEE, 5663–5670.

[62]

Meir Kalech and Avraham Natan. 2022. Model-based diagnosis of multi-agent systems: A survey. Proc. AAAI Conf. Artif. Intell. 36, 11 (June2022), 12334–12341. DOI:

[63]

Yiannis Kantaros, Meng Guo, and Michael M. Zavlanos. 2019. Temporal logic task planning and intermittent connectivity control of mobile robot networks. IEEE Trans. Automat. Control 64, 10 (2019), 4105–4120.

[64]

Yiannis Kantaros and George J. Pappas. 2019. Optimal temporal logic planning for multi-robot systems in uncertain semantic maps. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 4127–4132.

Digital Library

[65]

Lydia E. Kavraki and Steven M. LaValle. 2016. Motion planning. In Springer Handbook of Robotics. Springer, 139–162.

[66]

Lydia E. Kavraki, Petr Svestka, J.-C. Latombe, and Mark H. Overmars. 1996. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Trans. Robot. Autom. 12, 4 (1996), 566–580.

[67]

Eliahu Khalastchi and Meir Kalech. 2019. Fault detection and diagnosis in multi-robot systems: A survey. Sensors 19, 18 (2019). DOI:

[68]

Beomjoon Kim, Leslie Pack Kaelbling, and Tomás Lozano-Pérez. 2019. Adversarial actor-critic method for task and motion planning problems using planning experience. In AAAI Conference on Artificial Intelligence. 8017–8024.

Digital Library

[69]

G. Ayorkor Korsah, M. Bernardine Dias, and Anthony Stentz. 2013. A comprehensive taxonomy for multi-robot task allocation. Int. J. Robot. Res. 32, 12 (2013), 1495–1512.

Digital Library

[70]

Quang Duy Lã, Yong Huat Chew, and Boon-Hee Soong. 2016. Potential game theory. Springer International Publishing (2016).

[71]

Fabien Lagriffoul, Neil T. Dantam, Caelan Garrett, Aliakbar Akbari, Siddharth Srivastava, and Lydia E. Kavraki. 2018. Platform-independent benchmarks for task and motion planning. Robot. Autom. Lett. 3, 4 (2018), 3765–3772.

[72]

Steven M. LaValle. 2006. Planning Algorithms. Cambridge University Press.

[73]

Steven M. LaValle et al. 1998. Rapidly-exploring random trees: A new tool for path planning. (1998).

[74]

Ni Li, Charles Remeikas, Yunjun Xu, Suhada Jayasuriya, and Reza Ehsani. 2015. Task assignment and trajectory planning algorithm for a class of cooperative agricultural robots. J. Dynam. Syst., Meas., Contr. 137, 5 (052015).

[75]

Lars Lindemann, Jakub Nowak, Lukas Schönbächler, Meng Guo, Jana Tumova, and Dimos V. Dimarogonas. 2021. Coupled multi-robot systems under linear temporal logic and signal temporal logic tasks. IEEE Trans. Contr. Syst. Technol. 29, 2 (2021), 858–865.

[76]

Yugang Liu and Goldie Nejat. 2016. Multirobot cooperative learning for semiautonomous control in urban search and rescue applications. J. Field Robot. 33, 4 (2016), 512–536.

Digital Library

[77]

Yuanchang Liu, Rui Song, Richard Bucknall, and Xinyu Zhang. 2019. Intelligent multi-task allocation and planning for multiple unmanned surface vehicles (USVs) using self-organising maps and fast marching method. Inf. Sci. 496 (2019), 180–197.

Digital Library

[78]

Shih-Yun Lo, Shiqi Zhang, and Peter Stone. 2018. PETLON: Planning efficiently for task-level-optimal navigation. In 17th International Conference on Autonomous Agents and Multi-Agent Systems. 220–228.

[79]

Masoumeh Mansouri, Bruno Lacerda, Nick Hawes, and Federico Pecora. 2019. Multi-robot planning under uncertain travel times and safety constraints. In 28th International Joint Conference on Artificial Intelligence (IJCAI’19). 478–484.

Digital Library

[80]

Masoumeh Mansouri, Federico Pecora, and Peter Schüller. 2021. Combining task and motion planning: Challenges and guidelines. Front. Robot. AI 8 (2021). DOI:

[81]

Deborah L. McGuinness, Frank Van Harmelen, et al. 2004. OWL web ontology language overview. W3C Recommend. 10, 10 (2004), 2004.

[82]

Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. 2013. Playing Atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602 (2013).

[83]

James Motes, Read Sandström, Will Adams, Tobi Ogunyale, Shawna Thomas, and Nancy M. Amato. 2019. Interaction templates for multi-robot systems. Robot. Autom. Lett. 4, 3 (2019), 2926–2933.

[84]

James Motes, Read Sandström, Hannah Lee, Shawna Thomas, and Nancy M. Amato. 2020. Multi-robot task and motion planning with subtask dependencies. Robot. Autom. Lett. 5, 2 (2020), 3338–3345.

[85]

Roger B. Myerson. 1997. Game Theory: Analysis of Conflict. Harvard University Press.

[86]

Avraham Natan and Meir Kalech. 2022. Privacy-aware distributed diagnosis of multi-agent plans. Expert Syst. Applic. 192 (2022), 116313. DOI:

Digital Library

[87]

Jianjun Ni, Guangyi Tang, Zhengpei Mo, Weidong Cao, and Simon X. Yang. 2020. An improved potential game theory based method for multi-UAV cooperative search. IEEE Access 8 (2020), 47787–47796.

[88]

Alexandros Nikou, Jana Tumova, and Dimos V. Dimarogonas. 2017. Probabilistic plan synthesis for coupled multi-agent systems. IFAC-PapersOnLine 50, 1 (2017), 10766–10771.

[89]

Ernesto Nunes and Maria Gini. 2015. Multi-robot auctions for allocation of tasks with temporal constraints. In AAAI Conference on Artificial Intelligence.

[90]

Hyacinth S. Nwana. 1996. Software agents: An overview. Knowl. Eng. Rev. 11, 3 (1996), 205–244.

[91]

Shayegan Omidshafiei, Jason Pazis, Christopher Amato, Jonathan P. How, and John Vian. 2017. Deep decentralized multi-task multi-agent reinforcement learning under partial observability. In International Conference on Machine Learning. PMLR, 2681–2690.

Digital Library

[92]

Sotiris Papatheodorou, Michalis Smyrnakis, Tembine Hamidou, and Anthony Tzes. 2018. Path planning and task assignment for data retrieval from wireless sensor nodes relying on game-theoretic learning. In 5th International Conference on Control, Decision and Information Technologies (CoDIT). IEEE, 1073–1078.

[93]

Lynne E. Parker, Daniela Rus, and Gaurav S. Sukhatme. 2016. Multiple mobile robot systems. In Springer Handbook of Robotics. Springer, 1335–1384.

[94]

Alireza Partovi, Rafael Rodrigues da Silva, and Hai Lin. 2018. Reactive integrated mission and motion planning for mobile robotic manipulators. In Annual American Control Conference (ACC). 3538–3543.

[95]

Marco Pavone, Emilio Frazzoli, and Francesco Bullo. 2011. Adaptive and distributed algorithms for vehicle routing in a stochastic and dynamic environment. IEEE Trans. Automat. Control 56, 6 (2011), 1259–1274.

[96]

Chris Paxton, Vasumathi Raman, Gregory D. Hager, and Marin Kobilarov. 2017. Combining neural networks and tree search for task and motion planning in challenging environments. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 6059–6066.

Digital Library

[97]

Ana Pereira and Carsten Thomas. 2020. Challenges of machine learning applied to safety-critical cyber-physical systems. Mach. Learn. Knowl. Extract. 2, 4 (2020), 579–602.

[98]

Jan Peters and Stefan Schaal. 2008. Reinforcement learning of motor skills with policy gradients. Neural Netw. 21, 4 (2008), 682–697.

Digital Library

[99]

Camille Phiquepal and Marc Toussaint. 2019. Combined task and motion planning under partial observability: An optimization-based approach. In International Conference on Robotics and Automation (ICRA). IEEE, 9000–9006.

Digital Library

[100]

Erion Plaku and Duong Le. 2016. Interactive search for action and motion planning with dynamics. J. Experim. Theoret. Artif. Intell. 28, 5 (2016), 849–869.

[101]

Salar Rahili, Jiahui Lu, Wei Ren, and Ubaid M. Al-Saggaf. 2018. Distributed coverage control of mobile sensor networks in unknown environment using game theory: Algorithms and experiments. IEEE Trans. Mob. Comput. 17, 6 (2018), 1303–1313.

[102]

Colin R. Reeves (Ed.). 1993. Modern Heuristic Techniques for Combinatorial Problems. John Wiley & Sons, Inc.

Digital Library

[103]

John H. Reif. 1979. Complexity of the mover’s problem and generalizations. In 20th Annual Symposium on Foundations of Computer Science (SFCS’79). IEEE Computer Society, 421–427.

[104]

Yara Rizk, Mariette Awad, and Edward W. Tunstel. 2019. Cooperative heterogeneous multi-robot systems: A survey. ACM Comput. Surv. 52, 2 (2019), 1–31.

Digital Library

[105]

Elzbieta Roszkowska, Piotr Dulewicz, and Lukasz Janiec. 2019. Hierarchical hybrid control for multiple mobile robot systems. IFAC-PapersOnLine 52, 8 (2019), 452–457.

[106]

K. Savla, E. Frazzoli, and F. Bullo. 2005. On the point-to-point and traveling salesperson problems for Dubins’ vehicle. In American Control Conference.786–791. DOI:

[107]

Ketan Savla, Emilio Frazzoli, and Francesco Bullo. 2008. Traveling salesperson problems for the Dubins vehicle. IEEE Trans. Automat. Control 53, 6 (2008), 1378–1391.

[108]

Daigo Shishika, James Paulos, and Vijay Kumar. 2020. Cooperative team strategies for multi-player perimeter-defense games. Robot. Autom. Lett. 5, 2 (2020), 2738–2745.

[109]

David B. Shmoys and Éva Tardos. 1993. An approximation algorithm for the generalized assignment problem. Math. Program. 62, 1 (1993), 461–474.

[110]

Mohammed El Habib Souidi and Songhao Piao. 2016. A new decentralized approach of multiagent cooperative pursuit based on the iterated elimination of dominated strategies model. Math. Prob. Eng. 2016 (2016).

[111]

Siddharth Srivastava, Nishant Desai, Richard Freedman, and Shlomo Zilberstein. 2018. An anytime algorithm for task and motion mdps. arXiv preprint arXiv:1802.05835 (2018).

[112]

Richard S. Sutton and Andrew G. Barto. 2018. Reinforcement Learning: An Introduction. The MIT Press.

Digital Library

[113]

Kai Chuen Tan, Myungjin Jung, Isaac Shyu, Changhuang Wan, and Ran Dai. 2020. Motion planning and task allocation for a jumping rover team. In IEEE International Conference on Robotics and Automation (ICRA). IEEE, 5278–5283.

[114]

Wei N. Tang, Shuai D. Han, and Jingjin Yu. 2020. Computing high-quality clutter removal solutions for multiple robots. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 7963–7970.

Digital Library

[115]

Antony Thomas, Sunny Amatya, Fulvio Mastrogiovanni, and Marco Baglietto. 2019. Task-assisted motion planning in partially observable domains. arXiv preprint arXiv:1908.10227 (2019).

[116]

Antony Thomas, Fulvio Mastrogiovanni, and Marco Baglietto. 2019. Task-motion planning for navigation in belief space. arXiv preprint arXiv:1910.11683 (2019).

[117]

Antony Thomas, Fulvio Mastrogiovanni, and Marco Baglietto. 2020. Towards multi-robot task-motion planning for navigation in belief space. arXiv preprint arXiv:2010.00780 (2020).

[118]

Rodrigo Toro Icarte, Toryn Q. Klassen, Richard Valenzano, and Sheila A. McIlraith. 2018. Teaching multiple tasks to an RL agent using LTL. In 17th International Conference on Autonomous Agents and MultiAgent Systems. 452–461.

[119]

Paolo Toth and Daniele Vigo. 2002. 1. An Overview of Vehicle Routing Problems. 1–26. Retrieved from https://epubs.siam.org/doi/pdf/10.1137/1.9780898718515.ch1.

[120]

Jana Tumova and Dimos V. Dimarogonas. 2015. Decomposition of multi-agent planning under distributed motion and task LTL specifications. In 54th IEEE Conference on Decision and Control (CDC). IEEE, 7448–7453.

[121]

William Vega-Brown and Nicholas Roy. 2018. Admissible abstractions for near-optimal task and motion planning. In 27th International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, 4852–4859.

Digital Library

[122]

Isaac E. Weintraub, Meir Pachter, and Eloy Garcia. 2020. An introduction to pursuit-evasion differential games. In American Control Conference (ACC). IEEE, 1049–1066.

[123]

Bradley Woosley and Prithviraj Dasgupta. 2018. Integrated real-time task and motion planning for multiple robots under path and communication uncertainties. Robotica 36, 3 (2018), 353–373.

[124]

Bin Xin, Guan-Qiang Gao, Yu-Long Ding, Yang-Guang Zhu, and Hao Fang. 2017. Distributed multi-robot motion planning for cooperative multi-area coverage. In 13th IEEE International Conference on Control & Automation (ICCA). IEEE, 361–366.

[125]

Rui Yan, Zongying Shi, and Yisheng Zhong. 2019. Task assignment for multiplayer reach–avoid games in convex domains via analytical barriers. IEEE Trans. Robot. 36, 1 (2019), 107–124.

[126]

Zhi Yan, Nicolas Jouandeau, and Arab Ali Cherif. 2013. A survey and analysis of multi-robot coordination. Int. J. Adv. Robot. Syst. 10, 12 (2013), 399.

[127]

Chongjie Zhang and Julie A. Shah. 2016. Co-optimizing task and motion planning. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 4750–4756.

Digital Library

[128]

Kaiqing Zhang, Zhuoran Yang, and Tamer Başar. 2021. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handb. Reinforc. Learn. Contr. (2021), 321–384.

[129]

Huanfei Zheng and Yue Wang. 2019. A distributed framework for dynamic task allocation of multi-robot symbolic motion planning. In American Control Conference (ACC). IEEE, 3291–3296.

[130]

Robert Michael Zlot. 2006. An Auction-based Approach to Complex Task Allocation for Multirobot Teams. Ph.D. Dissertation. Robotics Institute, Carnegie Mellon University.

Cited By

Pey JSamarakoon SMuthugala MElara M(2025)A Decentralized Partially Observable Markov Decision Process for complete coverage onboard multiple shape changing reconfigurable robotsExpert Systems with Applications10.1016/j.eswa.2025.126565(126565)Online publication date: Jan-2025
https://doi.org/10.1016/j.eswa.2025.126565
Bakshi SSahu BKuanar S(2025)Task Assignment of Cooperating Robot in Multi-Robot EnvironmentIntelligent Systems10.1007/978-981-97-8160-7_8(91-100)Online publication date: 18-Jan-2025
https://doi.org/10.1007/978-981-97-8160-7_8
Mansouri MStreet CWarsame Y(2025)The CONVINCE Perspective on Task and Motion Planning in Dynamic EnvironmentsEuropean Robotics Forum 202410.1007/978-3-031-76428-8_39(206-210)Online publication date: 1-Jan-2025
https://doi.org/10.1007/978-3-031-76428-8_39
Show More Cited By

Index Terms

Multiple Mobile Robot Task and Motion Planning: A Survey
1. Computer systems organization
  1. Embedded and cyber-physical systems
    1. Robotics
2. Computing methodologies
  1. Artificial intelligence

Recommendations

A Hybrid Approach to Intricate Motion, Manipulation and Task Planning

We propose a representation and a planning algorithm able to deal with problems integrating task planning as well as motion and manipulation planning knowledge involving several robots and objects. Robot plans often include actions where the robot has to ...
Robot task planning using semantic maps

Task planning for mobile robots usually relies solely on spatial information and on shallow domain knowledge, such as labels attached to objects and places. Although spatial information is necessary for performing basic robot operations (navigation and ...
VCS-based motion planning for distributed mobile robots: collision avoidance and formation

This paper addresses decentralized motion planning among a homogeneous set of feedback-controlled mobile robots. It introduces the velocity obstacle, which describes the collision between robot and obstacle, and the hybrid interactive velocity obstacles ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Computing Surveys

ACM Computing Surveys Volume 55, Issue 10

October 2023

772 pages

ISSN:0360-0300

EISSN:1557-7341

DOI:10.1145/3567475

Editor:
Albert Zomaya
University of Sydney, Australia

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 February 2023

Online AM: 28 September 2022

Accepted: 14 September 2022

Revised: 06 September 2022

Received: 12 January 2022

Published in CSUR Volume 55, Issue 10

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Survey
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

40
Total Citations
View Citations
4,390
Total Downloads

Downloads (Last 12 months)1,593
Downloads (Last 6 weeks)160

Reflects downloads up to 01 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Pey JSamarakoon SMuthugala MElara M(2025)A Decentralized Partially Observable Markov Decision Process for complete coverage onboard multiple shape changing reconfigurable robotsExpert Systems with Applications10.1016/j.eswa.2025.126565(126565)Online publication date: Jan-2025
https://doi.org/10.1016/j.eswa.2025.126565
Bakshi SSahu BKuanar S(2025)Task Assignment of Cooperating Robot in Multi-Robot EnvironmentIntelligent Systems10.1007/978-981-97-8160-7_8(91-100)Online publication date: 18-Jan-2025
https://doi.org/10.1007/978-981-97-8160-7_8
Mansouri MStreet CWarsame Y(2025)The CONVINCE Perspective on Task and Motion Planning in Dynamic EnvironmentsEuropean Robotics Forum 202410.1007/978-3-031-76428-8_39(206-210)Online publication date: 1-Jan-2025
https://doi.org/10.1007/978-3-031-76428-8_39
Sikora TPapić V(2024)Survey of Path Planning for Aerial Drone Inspection of Multiple Moving ObjectsDrones10.3390/drones81207058:12(705)Online publication date: 26-Nov-2024
https://doi.org/10.3390/drones8120705
Liu LLiu HWang XLi JWang PLiu SZou JYang X(2024)Application of Path Planning and Tracking Control Technology in Mower RobotsAgronomy10.3390/agronomy1411247314:11(2473)Online publication date: 23-Oct-2024
https://doi.org/10.3390/agronomy14112473
Xiao SZheng CJin JLing RGuo X(2024)Design and Implementation of an Self-navigating Transportation Robot: A Visual Image Recognition-Based Approach2024 43rd Chinese Control Conference (CCC)10.23919/CCC63176.2024.10661587(4663-4668)Online publication date: 28-Jul-2024
https://doi.org/10.23919/CCC63176.2024.10661587
Xu GKang XYang HWu YLiu WCao JLiu Y(2024)Distributed Multi-Vehicle Task Assignment and Motion Planning in Dense EnvironmentsIEEE Transactions on Automation Science and Engineering10.1109/TASE.2023.333607621:4(7027-7039)Online publication date: Oct-2024
https://doi.org/10.1109/TASE.2023.3336076
Yan RDeng RLai HZhang WShi ZZhong Y(2024)Homicidal Chauffeur Reach-Avoid Games via Guaranteed Winning StrategiesIEEE Transactions on Automatic Control10.1109/TAC.2023.332969369:4(2367-2382)Online publication date: Apr-2024
https://doi.org/10.1109/TAC.2023.3329693
CHICAIZA FSLAWIñSKI EMUT V(2024)Delayed Bilateral Teleoperation of Mobile Manipulators With Hybrid Mapping: Rate/Nonlinear-Position ModesIEEE Open Journal of the Industrial Electronics Society10.1109/OJIES.2024.34194225(663-681)Online publication date: 2024
https://doi.org/10.1109/OJIES.2024.3419422
Schneider EWu DDas DChernova S(2024)CE-MRS: Contrastive Explanations for Multi-Robot SystemsIEEE Robotics and Automation Letters10.1109/LRA.2024.34697869:11(10121-10128)Online publication date: Nov-2024
https://doi.org/10.1109/LRA.2024.3469786
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Full Text

View this article in Full Text.

HTML Format

View this article in HTML Format.

Figures

Tables

Media

View full text|Download PDF

View Issue’s Table of Contents