Top

Autonomous Robots

Published in:

17-07-2019

Hybrid planning and distributed iterative repair for multi-robot missions with communication losses

Authors: Patrick Bechon, Charles Lesire, Magali Barbier

Published in: Autonomous Robots | Issue 3-4/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This paper presents a planning and execution architecture suited for the initial planning, the execution and the on-board repair of a plan for a multi-robot mission. The team as a whole must accomplish its mission while dealing with online events such as robots breaking down, new objectives for the team, late actions and intermittent communications. We have chosen a “plan then repair” approach where an initial plan is computed offline and updated online whenever disruptive events happen. We have defined an hybrid planner that mixes Partial Order Planning (POP) with a Hierarchical Task Network (HTN)-based modelling of actions. This planner, called HiPOP for Hierarchical Partial-Order Planner, computes plans with temporal flexibility (thus easing its execution) and abstract actions (thus easing the repair process). It uses a symbolic representation of the world and has been extended with geometrical reasoning to adapt to multi-robots missions. Plans are executed in a distributed way: each robot is responsible of executing its own actions, and to propagate delays in its local plan, taking benefit from the temporal flexibility of the plan. When an inconsistency or a failure arises, a distributed repair algorithm based on HiPOP is used to repair the plan, by iteratively removing actions in the plan in order to amend the global plan. This repair is done onboard one of the robot of the team, and takes care of partial communication. The whole architecture has been evaluated through several benchmarks, statistical simulations, and field experiments involving 8 robots.

previous article Hierarchical reinforcement learning via dynamic subspace search for multi-agent planning

next article Competition and cooperation in a community of autonomous agents

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

ACTION was a project of ONERA and LAAS-CNRS, funded by the French Procurement Agency. The work described here was used for the final demonstration of the project. For more information, see http://action.onera.fr/.

Similar results were obtained on other domains of the International Planning Competition (IPC) not shown here because of lack of space.

Abichandani, P., Benson, H.Y., & Kam, M. (2013). Robust communication connectivity for multi-robot path coordination using mixed integer nonlinear programming: formulation and feasibility analysis. In International Conference on Robotics and Automation (ICRA), Karlsruhe, Germany.

Amigoni, F., Banfi, J., & Basilico, N. (2017). Multirobot exploration of communication-restricted environments: A survey. IEEE Intelligent Systems, 32(6), 48–57.CrossRef

Arrichiello, F., Marino, A., & Pierri, F. (2015). Observer-based decentralized fault detection and isolation strategy for networked multirobot systems. IEEE Transactions on Control Systems Technology, 23(4), 1465–1476. https://doi.org/10.1109/TCST.2014.2377175.CrossRef

Bajada, J., Fox, M., & Long, D. (2014). Temporal plan quality improvement and repair using local search. In Starting AI Researcher Symposium (STAIRS), Prague, Czech Republic.

Banfi, J., Li, A.Q., Basilico, N., Rekleitis, I., & Amigoni, F. (2016). Asynchronous multirobot exploration under recurrent connectivity constraints. In /textitInternational Conference on Robotics and Automation (ICRA) 2016-June: 5491–5498. https://doi.org/10.1109/ICRA.2016.7487763, http://ieeexplore.ieee.org/abstract/document/7487763/

Barbulescu, L., Rubinstein, Z.B., & Smith, S.F. (2010). Distributed coordination of mobile agent teams: The advantage of planning ahead. In International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), Toronto, Canada.

Bechon, P., Barbier, M., Infantes, G., Lesire, C., & Vidal, V. (2014). HiPOP : Hierarchical Partial-Order Planning. In Starting AI Researcher Symposium (STAIRS), Prague, Czech Republic.

Bechon, P., Barbier, M., Infantes, G., Lesire, C., & Vidal, V. (2015). Using hybrid planning for plan reparation. In European Conference on Mobile Robots (ECMR), Lincoln, UK.

Bercher, P., Biundo, S., Geier, T., Hoernle, T., Nothdurft, F., Richter, F., & Schattenberg, B. (2014). Plan, repair, execute, explain—How planning helps to assemble your home theater. In International Conference on Automated Planning & Scheduling (ICAPS), Portsmouth, NH, USA.

Bidot, J., Schattenberg, B., & Biundo, S. (2008). Plan repair in hybrid planning. In German Conferance on Artificial Intelligence (KI), Kaiserslautern, Germany.

Blum, A. L., & Furst, M. L. (1997). Fast planning through planning graph analysis. Artificial intelligence, 90, 1–2.MathSciNetCrossRef

Boella, G., & Damiano, R. (2002). A replanning algorithm for a reactive agent architecture. In: D. Scott (Ed.), Artificial intelligence: Methodology, systems, and applications. AIMSA 2002. Lecture Notes in Computer Science, vol 2443. Springer, Berlin, Heidelberg.

Brinon-Arranz, L., Schenato, L., & Seuret, A. (2015). Distributed source seeking via a circular formation of agents under communication constraints. IEEE Transactions on Control of Network Systems, 3(2), 104–115.MathSciNetCrossRef

Castillo, L., Fdez-Olivares, J., García-Pérez, Ó., & Palao, F. (2006). Efficiently handling temporal knowledge in an HTN planner. In International Conference on Automated Planning & Scheduling (ICAPS), Cumbria, UK.

Cubber, G.D., Doroftei, D., Baudoin, Y., Serrano, D., Chintamani, K., Sabino, R., & Ourevitch, S. (2012). ICARUS: An EU-FP7 project providing unmanned search and rescue tools. In IROS 2012 Workshop ROSIN, Vilamoura-Algarve, Portugal.

Dames, P. (2017). Distributed multi-target search and tracking using the PHD filter. International Symposium on Multi-Robot and Multi-Agent Systems (MRS) (pp. 1–8). https://doi.org/10.1109/MRS.2017.8250924. http://ieeexplore.ieee.org/document/8250924/.

Dechter, R., Meiri, I., & Pearl, J. (1991). Temporal constraint networks. Artificial intelligence, 49(1), 61–95.MathSciNetCrossRef

Drabble, B., Dalton, J., & Tate, A. (1997). Repairing plans on-the-fly. In International Workshop on Planning and Scheduling for Space (IWPSS), Oxnard, CA, USA.

Dvorak, F., Bartak, R., Bit-Monnot, A., Ingrand, F., & Ghallab, M. (2014). Planning and acting with temporal and hierarchical decomposition models. In International Conference on Tools with Artificial Intelligence (ICTAI), Limassol, Cyprus.

Echeverria, G., Lemaignan, S., Degroote, A., Lacroix, S., Karg, M., Koch, P., Lesire, C., & Stinckwich, S. (2012). Simulating complex robotic scenarios with MORSE. In International Conference on Simulation, Modeling, and Programming for Autonomous Robots (SIMPAR), Tsukuba, Japan.

Erol, K., Nau, D. S., & Subrahmanian, V. (1995). Complexity, decidability and undecidability results for domain-independent planning. Artificial Intelligence, 76(1–2).

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

Fox, M., & Long, D. (2003). PDDL2.1: An extension to PDDL for expressing temporal planning domains. Journal of Artificial Intelligence Research (JAIR), 20, 61–124.CrossRef

Fox, M., Gerevini, A., Long, D., & Serina, I. (2006). Plan stability: Replanning versus plan repair. In International Conference on Automated Planning & Scheduling (ICAPS), Cumbria, UK.

Franchi, A., Stegagno, P., & Oriolo, G. (2016). Decentralized multi-robot encirclement of a 3D target with guaranteed collision avoidance. Autonomous Robots, 40(2), 245–265. https://doi.org/10.1007/s10514-015-9450-3. arXiv:1307.7170.CrossRef

Garzón, M., Valente, J., Roldán, J. J., Cancar, L., Barrientos, A., & Del Cerro, J. (2016). A multirobot system for distributed area coverage and signal searching in large outdoor scenarios. Journal of Field Robotics, 33(8), 1087–1106. https://doi.org/10.1002/rob.21636.CrossRef

Gerevini, A., & Serina, I. (2000). Fast plan adaptation through planning graphs: Local and systematic search techniques. In International Conference on Artificial Intelligence Planning Systems (AIPS), Toronto, Canada.

Goldman, R. (2006). Durative Planning in HTNs. In International Conference on Automated Planning & Scheduling (ICAPS), Cumbria, UK.

Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the Heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107. https://doi.org/10.1109/TSSC.1968.300136.CrossRef

Hashmi, M.A., Seghrouchni, A.E.F. (2010). Merging of temporal plans supported by plan repairing. In International Conference on Tools with Artificial Intelligence (ICTAI), Arras, France.

Haslum, P., & Geffner, H. (2000). Admissible Heuristics for optimal planning. In International Conference on Artificial Intelligence Planning Systems (AIPS), Toronto, Canada.

Hoffmann, J., & Nebel, B. (2011). The FF planning system: Fast plan generation through heuristic search. Journal of Artificial Intelligence Research (JAIR), 14(1).

Hoffmann, J., Porteous, J., & Sebastia, L. (2004). Ordered landmarks in planning. Journal of Artificial Intelligence Research (JAIR), 22(1), 215–278.MathSciNetCrossRef

Kambhampati, S., Mali, A., & Srivastava, B. (1998). Hybrid planning for partially hierarchical domains. In National Conference on Artificial Intelligence (AAAI), Madison, WI, USA.

Khadka, S., Chung, J.J., & Tumer, K. (2017). Memory-augmented multi-robot teams that learn to adapt. International Planning Competition (IPC) http://ieeexplore.ieee.org/abstract/document/8250941/.

Krogt, R.V.D., & Weerdt, M.D. (2005). Plan repair as an extension of planning. In International Conference on Automated Planning & Scheduling (ICAPS), Monterey, CA, USA.

Lesire, C., Infantes, G., Gateau, T., & Barbier, M. (2016). A distributed architecture for supervision of autonomous multi-robot missions—application to air-sea scenarios. Auton Robots, 40(7).

Luo, L., Chakraborty, N., & Sycara, K. (2013). Distributed algorithm design for multi-robot task assignment with deadlines for tasks. In International Conference on Robotics and Automation (ICRA), Karlsruhe, Germany.

Marconi, L., Melchiorri, C., Beetz, M., Pangercic, D., Siegwart, R., Leutenegger, S., Carloni, R., Stramigioli, S., Bruyninckx, H., Doherty, P., Kleiner, A., Lippiello, V., Finzi, A., Siciliano, B., Sala, A., & Tomatis, N. (2012). The SHERPA project: Smart collaboration between humans and ground-aerial robots for improving rescuing activities in alpine environments. In International Symposium on Robotic Reseach (ISRR), College Station, TX, USA.

McDermott, D., Ghallab, M., Howe, A., Knoblock, C., Ram, A., & Veloso, M., et al. (1998). PDDL-the planning domain definition language. Tech. rep., Yale Center for Computational Vision and Control.

Moarref, S., & Kress-Gazit, H. (2017). Decentralized control of robotic swarms from high-level temporal logic specifications. In International Symposium on Multi-Robot and Multi-Agent Systems (MRS) pp 17–23, http://ieeexplore.ieee.org/abstract/document/8250926/.

Nau, D., Ghallab, M., & Traverso, P. (2004). Automated Planning: Theory & Practice. San Francisco: Morgan Kaufmann Publishers Inc.MATH

Nau, D.S., Cao, Y., Lotem, A., & Muñoz-Avila, H. (1999). SHOP: Simple hierarchical ordered planner. In International Joint Conference on Artificial Intelligence (IJCAI), Stockholm, Sweden.

Nau, D. S., Au, T. C., Ilghami, O., Kuter, U., Murdock, J. W., Wu, D., et al. (2003). SHOP2: An HTN planning system. Journal of Artificial Intelligence Research (JAIR), 20(1), 379–404.CrossRef

Otte, M., Kuhlman, M., & Sofge, D. (2017). Multi-robot task allocation with auctions in harsh communication environments. In International Symposium on Multi-Robot and Multi-Agent Systems (MRS) pp 32–39, http://ieeexplore.ieee.org/abstract/document/8250928/.

Parker, L. (2008). Distributed intelligence: overview of the field and its application in multi-robot systems. Journal of Physical Agents, 2(2), 5–14.

Pei, Y., & Mutka, M.W. (2012). Steiner traveler: Relay deployment for remote sensing in heterogeneous multi-robot exploration. In International Conference on Robotics and Automation (ICRA), St. Paul, MN, USA.

Penberthy, J.S., & Weld, D.S. (1992). UCPOP: A sound, complete, partial order planner for ADL. In International Conference on Principles of Knowledge Representation and Reasoning (KR), Cambridge, MA, USA.

Penumarthi, P.K., Li, A.Q., Banfi, J., Basilico, N., Amigoni, F., O’Kane, J., Rekleitis, I., & Nelakuditi, S. (2017). Multirobot exploration for building communication maps with prior from communication models. In International Symposium on Multi-Robot and Multi-Agent Systems (MRS) https://cse.sc.edu/~penumarp/MRS17.pdf.

Ponda, S., Redding, J., Choi, H.L., How, J.P., Vavrina, M., & Vian, J. (2010). Decentralized planning for complex missions with dynamic communication constraints. In American Control Conference (ACC), Baltimore, MD, USA.

Portugal, D., & Rocha, R. P. (2016). Cooperative multi-robot patrol with Bayesian learning. Autonomous Robots, 40(5), 929–953. https://doi.org/10.1007/s10514-015-9503-7.CrossRef

Pralet, C., & Lesire, C. (2014). Deployment of mobile wireless sensor networks for crisis management: A constraint-based local search approach. In International Conference on Principles and Practice of Constraint Programming (CP), Lyon, France.

Richter, S., Helmert, M., & Westphal, M. (2008). Landmarks Revisited. In International Conference on Artificial Intelligence (AAAI), Chicago, IL, USA.

Röger, G., Eyerich, P., & Mattmüller, R. (2008). TFD: A numeric temporal extension to Fast Downward. In International Planning Competition (IPC), Syndey, Australia.

Schattenberg, B. (2009). Hybrid Planning And Scheduling. PhD thesis, Ulm University, Institute of Artificial Intelligence.

Stock, S., Mansouri, M., Pecora, F., & Hertzberg, J. (2015) Online task merging with a hierarchical hybrid task planner for mobile service robots. In International Conference on Intelligent Robots and Systems (IROS), Hamburg, Germany.

Vidal, V. (2011). YAHSP2: Keep it simple, stupid. In International Planning Competition (IPC), Freiburg, Germany.

Warfield, I., Hogg, C., Lee-Urban, S., & Muñoz-Avila, H. (2007). Adaptation of Hierarchical Task Network Plans. In FLAIRS Conference, Key West, FL, USA.

Younes, H., & Simmons, R. (2003). VHPOP: Versatile heuristic partial order planner. Journal of Artificial Intelligence Research (JAIR), 20, 405–430.CrossRef

Title: Hybrid planning and distributed iterative repair for multi-robot missions with communication losses
Authors: Patrick Bechon
Charles Lesire
Magali Barbier
Publication date: 17-07-2019
Publisher: Springer US
Published in: Autonomous Robots / Issue 3-4/2020
Print ISSN: 0929-5593
Electronic ISSN: 1573-7527
DOI: https://doi.org/10.1007/s10514-019-09869-w

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Other articles of this Issue 3-4/2020

Average case constant factor time and distance optimal multi-robot path planning in well-connected environments

Cooperative Queuing Policies for Effective Scheduling of Operator Intervention

Adaptive target tracking with a mixed team of static and mobile guards: deployment and activation strategies

Air-ground cooperative topometric mapping of traversable ground

A robust localization system for multi-robot formations based on an extension of a Gaussian mixture probability hypothesis density filter

Cooperative visual-inertial sensor fusion: fundamental equations and state determination in closed-form