Skip to main content
Springer Nature Link
Log in

Multi-robot planning with conflicts and synergies

  • Published:
Autonomous Robots Aims and scope Submit manuscript

Abstract

Multi-robot planning (mrp) aims at computing plans, each in the form of a sequence of actions, for a team of robots to achieve their individual goals, while minimizing overall cost. Solving mrp problems requires modeling limited domain resources (e.g., corridors that allow at most one robot at a time), and the possibility of action synergy (e.g., multiple robots going through a door after a single door-opening action). Optimally solving mrp problems is hard as it is a generalization of the single agent planning domain which is known to be NP-hard, and frequently requires considering the states of all the robots, resulting in an exponentially growing joint state and action space. In many mrp domains, robots encounter situations where they have conflicting needs for constrained resources, or where they can take advantage of what each other is doing to form synergies. In this article, we formulate the problem of multi-robot planning with conflicts and synergies (mrpcs), and develop a multi-robot planning framework, called iterative inter-dependent planning (iidp), for representing and solving mrpcs problems. Within the iidp framework, we develop the algorithms of increasing dependency and best alternative which exhibit different trade-offs between plan quality and computational efficiency. Extensive experiments covering the suggested algorithms have been performed using both an abstract-domain simulator, where we can automatically generate a variety of domain configurations, and a practical mrpcs instantiation that focuses on multi-robot navigation. In the navigation domain, we model plan costs with temporal uncertainty, and present a novel shifted-Poisson distribution for accumulating temporal uncertainty over actions. In comparison to baseline approaches, our algorithms produce significant reductions in overall plan cost, while avoiding search in the joint state space. In addition, we present a complete demonstration of the implementation of the model on a team of real robots.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. This article is based upon a previous conference publication (Zhang et al. 2017). It extends the conference paper in formalizing a framework for multi-robot planning, proposing a novel algorithm, and testing the algorithms on larger scale problems of up to 50 agents as opposed to 3. None of the material (including the conference paper) has appeared in any other journal submission.

  2. Ties can be broken in favor of the agent with the longest action sequence or by any other metric.

  3. Note that in this example best alternative performs the same as increasing dependency and so we only refer to increasing dependency.

  4. For example, such delays can be caused by forcing the robot to stop and say “excuse me” as is done by CoBots Veloso et al. (2015).

  5. In implementation, the integrals are replaced by summation operations, because action completions only happen at specific time instances (e.g., Fig. 7).

  6. The code for our simulated environment is publicly available at https://github.com/YuqianJiang/multi_agent_planning.

  7. If two robots try to pass each other, there is a significant risk that they will bump into each other and become entangled. In contrast, at least in our environment, we find that most people give way to the robots by standing close to the wall.

References

  • Alonso-Mora, J., DeCastro, J. A., Raman, V., Rus, D., & Kress-Gazit, H. (2018). Reactive mission and motion planning with deadlock resolution avoiding dynamic obstacles. Autonomous Robots, 42(4), 801–824.

    Article  Google Scholar 

  • Alur, R., Moarref, S., & Topcu, U. (2013). Counter-strategy guided refinement of gr (1) temporal logic specifications. In Formal Methods in Computer-Aided Design (FMCAD), IEEE, 2013, (pp. 26–33).

  • Amato, C., Konidaris, G., Cruz, G., Maynor, C. A., How, J. P., & Kaelbling, L. P. (2015). Planning for decentralized control of multiple robots under uncertainty. In 2015 IEEE International Conference on Robotics and Automation (ICRA), (pp. 1241–1248).

  • Boutilier, C., & Brafman, R. I. (2001). Partial-order planning with concurrent interacting actions. Journal of Artificial Intelligence Research, 14, 105–136.

    Article  Google Scholar 

  • Brafman, R. I., & Domshlak, C. (2008). From one to many: Planning for loosely coupled multi-agent systems. In ICAPS, 28–35.

  • Brenner, M. (2003). A multiagent planning language. In Proceedings of the Workshop on PDDL, ICAPS, Vol. 3, (pp. 33–38).

  • Brooks, J., Reed, E., Gruver, A., & Boerkoel Jr., J. C. (2015). Robustness in probabilistic temporal planning. In National Conference on Artificial Intelligence (AAAI).

  • Brucker, P. (2007). Scheduling algorithms. Berlin: Springer.

    MATH  Google Scholar 

  • Buehler, J., & Pagnucco, M. (2014). A framework for task planning in heterogeneous multi robot systems based on robot capabilities. In Twenty-Eighth AAAI Conference on Artificial Intelligence.

  • Coltin, B., & Veloso, M. (2014). Scheduling for transfers in pickup and delivery problems with very large neighborhood search. In Twenty-Eighth AAAI Conference on Artificial Intelligence.

  • Crosby, M., Rovatsos, M., & Petrick, R. P. (2013). Automated agent decomposition for classical planning. In ICAPS, 46–54.

  • Dresner, K., & Stone, P. (2008). A multiagent approach to autonomous intersection management. Journal of Artificial Intelligence Research, 31, 591–656.

    Article  Google Scholar 

  • Fentanes, J. P., Lacerda, B., Krajnik, T., Hawes, N., & Hanheide, M. (2015). Now or later? predicting and maximising success of navigation actions from long-term experience. In IEEE International Conference on Robotics and Automation (ICRA), (pp. 1112–1117).

  • Ferreira, P. R., dos Santos, F., Bazzan, A. L. C., Epstein, D., & Waskow, S. J. (2009). Robocup rescue as multiagent task allocation among teams: experiments with task interdependencies. Autonomous Agents and Multi-Agent Systems, 20, 421–443.

    Article  Google Scholar 

  • Fikes, R. E., & Nilsson, N. J. (1972). Strips: A new approach to the application of theorem proving to problem solving. Artificial intelligence, 2(3), 189–208.

    MATH  Google Scholar 

  • Filippidis, I., Dimarogonas, D. V., & Kyriakopoulos, K. J. (2012). Decentralized multi-agent control from local ltl specifications. In 2012 IEEE 51st IEEE Conference on Decision and Control (CDC), (pp. 6235–6240).

  • Gebser, M., Kaminski, R., Kaufmann, B., & Schaub, T. (2014). Clingo = ASP + control: Preliminary report. CoRR, abs/1405.3694.

  • Gelfond, M., & Lifschitz, V. (1998). Action languages. Electronic Transactions on Artificial Intelligence, 3, 195–210.

    MathSciNet  Google Scholar 

  • Gerkey, B. P., & Matarić, M. J. (2004). A formal analysis and taxonomy of task allocation in multi-robot systems. The International Journal of Robotics Research (IJRR), 23(9), 939–954.

    Article  Google Scholar 

  • Ghallab, M., Knoblock, C., Wilkins, D., Barrett, A., Christianson, D., Friedman, M., Kwok, C., Golden, K., Penberthy, S., Smith, D. E., Ying, S., Weld, D. (1998). Pddl-the planning domain definition language. 501–510.

  • Guo, X., & Hernández-Lerma, O. (2009). Continuous-time Markov decision processes. Berlin: Springer.

    Book  Google Scholar 

  • Helmert, M. (2006). The fast downward planning system. Journal of Artificial Intelligent Research, 26, 191–246.

    Article  Google Scholar 

  • Hoang, K. D., Fioretto, F., Hou, P., Yokoo, M., Yeoh, W., Zivan, R. (2016). Proactive dynamic distributed constraint optimization. In Proceedings of the 2016 international conference on autonomous agents & multiagent systems. International Foundation for Autonomous Agents and Multiagent Systems, (pp. 597–605).

  • Hoffmann, J., & Nebel, B. (2001). The ff planning system: Fast plan generation through heuristic search. Journal of Artificial Intelligence Research, 14, 253–302.

    Article  Google Scholar 

  • Hönig, W., Kumar, T. S., Cohen, L., Ma, H., Xu, H., Ayanian, N., & Koenig, S. (2016). Multi-agent path finding with kinematic constraints. In ICAPS, 477–485.

  • Jain, M., Taylor, M. E., Yokoo, M., & Tambe, M. (2009). DCOPs meet the real world: Exploring unknown reward matrices with applications to mobile sensor networks. In Proceedings of the International Joint Conference on Artificial Intelligence.

  • Khandelwal, P., Barrett, S., & Stone, P. (2015). Leading the way: An efficient multi-robot guidance system. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems, (pp. 1625–1633).

  • Khandelwal, P., Yang, F., Leonetti, M., Lifschitz, V., & Stone, P. (2014). Planning in Action Language \(\cal{B}\cal{C}\) while Learning Action Costs for Mobile Robots. In International Conference on Automated Planning and Scheduling (ICAPS).

  • Khandelwal, P., Zhang, S., Sinapov, J., Leonetti, M., Thomason, J., Yang, F., Gori, I., Svetlik, M., Khante, P., & Lifschitz, V. et al. (2017) Bwibots: A platform for bridging the gap between ai and human–robot interaction research. The International Journal of Robotics Research.

  • Knepper, R. A., Layton, T., Romanishin, J., & Rus, D. (2013). Ikeabot: An autonomous multi-robot coordinated furniture assembly system. In Robotics and Automation (ICRA), 2013 IEEE International Conference on, (pp. 855–862).

  • Knill, O. (1994). Probability and stochastic processes with applications. Overseas Press.

  • Koenig, N., & Howard, A. (2004). Design and use paradigms for gazebo, an open-source multi-robot simulator. In Intelligent Robots and Systems, 2004.(IROS 2004). Proceedings. 2004 IEEE/RSJ International Conference on, Vol. 3, pp. 2149–2154.

  • Komenda, A., et al. (2016). Privacy-concerned multiagent planning. Knowledge and Information Systems, 48(3), 581–618.

    Article  MathSciNet  Google Scholar 

  • Korsah, G. A., Stentz, A., & Dias, M. B. (2013). A comprehensive taxonomy for multi-robot task allocation. The International Journal of Robotics Research, 32(12), 1495–1512.

    Article  Google Scholar 

  • Kovács, D. L. (2012). A multi-agent extension of pddl3. 1.

  • Lee, J., Lifschitz, V., & Yang, F. (2013). Action language bc: Preliminary report. In Proceedings of the Twenty-Third international joint conference on Artificial Intelligence, pp. 983–989. AAAI Press.

  • Lesser, V., Ortiz, C. L, Jr., & Tambe, M. (2012). Distributed sensor networks: A multiagent perspective (Vol. 9). Berlin: Springer.

    MATH  Google Scholar 

  • Ma, H., & Koenig, S. (May 2016). Optimal target assignment and path finding for teams of agents. In International Conference on Autonomous Agents and Multiagent Systems (AAMAS).

  • Maheswaran, R. T., Pearce, J. P., & Tambe, M. (2004). Distributed algorithms for dcop: A graphical-game-based approach. In Parallel and Distributed Computing Systems (PDCS), (pp. 432–439).

  • Matsui, T., Matsuo, H., Silaghi, M., Hirayama, K., & Yokoo, M. (2008). Resource constrained distributed constraint optimization with virtual variables. In AAAI, (pp. 120–125).

  • Mausam, & Weld, D. S. (2008). Planning with durative actions in stochastic domains. Journal of Artificial Intelligence Research, 31, 33–82.

    Article  MathSciNet  Google Scholar 

  • Modi, P. J., Shen, W.-M., Tambe, M., & Yokoo, M. (2003). An asynchronous complete method for distributed constraint optimization. AAMAS, 3, 161–168.

    Article  Google Scholar 

  • Nilsson, N. J. (1984). Shakey the robot. Technical report, SRI INTERNATIONAL MENLO PARK CA.

  • Oglietti, M., Cesta, A. (2004). Cstrips: Towards explicit concurrent planning. In Proceedings of the 3rd Italian WS on Plan. and Sched., 9th National Symposium of Association Italiana per l’Int. Artif, (pp. 1–13).

  • Raman, V., Piterman, N., & Kress-Gazit, H. (2013). Provably correct continuous control for high-level robot behaviors with actions of arbitrary execution durations. In Robotics and Automation (ICRA), 2013 IEEE International Conference , (pp. 4075–4081).

  • Schäpers, B., Niemueller, T., Lakemeyer, G., Gebser, M., & Schaub, T. (2018). Asp-based time-bounded planning for logistics robots. In ICAPS, (pp. 509–517).

  • Sharon, G., Stern, R., Felner, A., & Sturtevant, N. R. (2015). Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence, 219, 40–66.

    Article  MathSciNet  Google Scholar 

  • Sharon, G., Stern, R., Goldenberg, M., & Felner, A. (2013). The increasing cost tree search for optimal multi-agent pathfinding. Artificial Intelligence, 195, 470–495.

    Article  MathSciNet  Google Scholar 

  • Smith, D. E., & Weld, D. S. (1999). Temporal planning with mutual exclusion reasoning. IJCAI, 99, 326–337.

    Google Scholar 

  • Tsugawa, S., & Kato, S. (2010). Energy its: another application of vehicular communications. IEEE Communications Magazine, 48(11), 120–126.

    Article  Google Scholar 

  • Turpin, M., Michael, N., & Kumar, V. (2014). Capt: Concurrent assignment and planning of trajectories for multiple robots. The International Journal of Robotics Research, 33(1), 98–112.

    Article  Google Scholar 

  • Veloso, M. M., Biswas, J., Coltin, B., & Rosenthal, S. (2015). CoBots: Robust symbiotic autonomous mobile service robots. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI).

  • Wagner, G., & Choset, H. (2015). Subdimensional expansion for multirobot path planning. Artificial Intelligence, 219, 1–24.

    Article  MathSciNet  Google Scholar 

  • Wong, K. W., & Kress-Gazit, H. (2015). Let’s talk: Autonomous conflict resolution for robots carrying out individual high-level tasks in a shared workspace. In Robotics and Automation (ICRA), 2015 IEEE International Conference , (pp. 339–345).

  • Wong, K. W., & Kress-Gazit, H. (2016). Need-based coordination for decentralized high-level robot control. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS).

  • Yedidsion, H., & Zivan, R. (2016). Applying dcop\_mst to a team of mobile robots with directional sensing abilities. In Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, pp. 1357–1358. International Foundation for Autonomous Agents and Multiagent Systems.

  • Younes, H. L., & Simmons, R. G. (2004). Solving generalized semi-markov decision processes using continuous phase-type distributions. In The AAAI Conference on Artificial Intelligence.

  • Zhang, S., Jiang, Y., Sharon, G., & Stone, P. (2017). Multirobot symbolic planning under temporal uncertainty. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems, pages 501–510. International Foundation for Autonomous Agents and Multiagent Systems.

  • Zhang, S., Sridharan, M., & Washington, C. (2013). Active visual planning for mobile robot teams using hierarchical POMDPs. IEEE Transactions on Robotics, 29(4), 975–985.

    Article  Google Scholar 

  • Zhang, S., Yang, F., Khandelwal, P., & Stone, P. (September 2015). Mobile robot planning using action language bc with an abstraction hierarchy. In Proceedings of the 13th International Conference on Logic Programming and Non-monotonic Reasoning (LPNMR), Lexington, KY, USA.

  • Zhang, Y., Parker, L. E. (2013). Multi-robot task scheduling. In IEEE International Conference on Robotics and Automation (ICRA), (pp. 2992–2998).

  • Zivan, R., Yedidsion, H., Okamoto, S., Glinton, R., & Sycara, K. P. (2015). Distributed constraint optimization for teams of mobile sensing agents. Journal of Autonomous Agents and Multi-Agent Systems, 29, 495–536.

    Article  Google Scholar 

Download references

Acknowledgements

This work has taken place in the Learning Agents Research Group (LARG) at the Artificial Intelligence Laboratory, The University of Texas at Austin. LARG research is supported in part by grants from the National Science Foundation (IIS-1637736, IIS-1651089, IIS-1724157), the Office of Naval Research (N00014-18-2243), Future of Life Institute (RFP2-000), DARPA, Intel, Raytheon, and Lockheed Martin. Peter Stone serves on the Board of Directors of Cogitai, Inc. The terms of this arrangement have been reviewed and approved by the University of Texas at Austin in accordance with its policy on objectivity in research.

Author information

Authors and Affiliations

  1. Department of Computer Science, The University of Texas, Austin, USA

    Yuqian Jiang, Harel Yedidsion & Peter Stone

  2. Department of Computer Science, The State University of New York, Binghamton, USA

    Shiqi Zhang

  3. Computer Science & Engineering, Texas A&M University, Texas, USA

    Guni Sharon

Authors
  1. Yuqian Jiang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Harel Yedidsion
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Shiqi Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Guni Sharon
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Peter Stone
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Harel Yedidsion.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Jiang, Y., Yedidsion, H., Zhang, S. et al. Multi-robot planning with conflicts and synergies. Auton Robot 43, 2011–2032 (2019). https://doi.org/10.1007/s10514-019-09848-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10514-019-09848-1

Keywords

Search

Navigation