Top

Information Systems Frontiers

Published in:

19-05-2018

Integrated Synthesis and Execution of Optimal Plans for Multi-Robot Systems in Logistics

Authors: Francesco Leofante, Erika Ábrahám, Tim Niemueller, Gerhard Lakemeyer, Armando Tacchella

Published in: Information Systems Frontiers | Issue 1/2019

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

search-config

AI-assisted search

Off

Abstract

Model-based synthesis allows to generate plans to achieve high-level tasks while satisfying certain properties of interest. However, when such plans are executed on concrete systems, several modeling assumptions may be challenged, jeopardizing their real applicability. This paper presents an integrated system for generating, executing and monitoring optimal-by-construction plans for multi-robot systems. This system unites the power of Optimization Modulo Theories with the flexibility of an on-line executive, providing optimal solutions for high-level task planning, and runtime feedback on their feasibility. After presenting how our system orchestrates static and runtime components, we demonstrate its capabilities using the RoboCup Logistics League as testbed. We do not only present our final solution but also its chronological development, and draw some general observations for the development of OMT-based approaches.

previous article Quantitative Analysis of Apache Storm Applications: The NewsAsset Case Study

next article Extracting Knowledge from Technical Reports for the Valuation of West Texas Intermediate Crude Oil Futures

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

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

http://www.robocup-logistics.org/sim-comp

Fawkes is a component-based software framework for robotic real-time applications. URL: www.fawkesrobotics.org

https://developers.google.com/protocol-buffers/

Running on a machine running Ubuntu Mate 16.4, Intel Core i7 CPU at 2.10GHz and 8GB of RAM

Available at https://www.fawkesrobotics.org/projects/rcll-sim/

We use a machine running Debian 9, Intel Core 2 Quad CPU Q9450 at 2.66 GHz.

Makespan for non-temporal POPF with single robot is computed as follows. We read the sequence of actions contained in the plan and assign to each the same duration specified in the temporal models used by other approaches.

https://www.darpa.mil/attachments/DARPA-BAA-16-53.pdf

https://smtlib.github.io/jSMTLIB/SMTLIBTutorial.pdf

Ábrahám, E, & Kremer, G. (2016). Satisfiability checking: theory and applications. In Proc. of SEFM’16 (pp. 9–23).

Bensalem, S., Havelund, K., Orlandini, A. (2014). Verification and validation meet planning and scheduling. STTT, 16(1), 1–12.CrossRef

Berry, G., & Gonthier, G. (1992). The Esterel synchronous programming language: design, semantics, implementation. Science of Computer Programming, 19(2), 87–152.CrossRef

Biere, A., Cimatti, A., Clarke, E.M., Zhu, Y. (1999). Symbolic model checking without BDDs. In Proc. of TACAS’99 (pp. 193–207).

Bjørner, N., Phan, A., Fleckenstein, L. (2015). ν z - An optimizing SMT solver. In Proc. of TACAS’15 (pp. 194—199).

Cashmore, M., Fox, M., Long, D., Magazzeni, D., Ridder, B., Carrera, A., Palomeras, N., Hurtȯs, N, Carreras, M. (2015). Rosplan: Planning in the robot operating system. In Proc. of ICAPS’15 (pp. 333–341).

Cashmore, M., Fox, M., Long, D., Magazzeni, D. (2016). A compilation of the full PDDL + language into SMT. In Proc. of ICAPS’16 (pp. 79–87).

Cimatti, A., Franzėn, A, Griggio, A., Sebastiani, R., Stenico, C. (2010). Satisfiability modulo the theory of costs: foundations and applications. In Proc. of TACAS’10 (pp. 99–113).

Coles, A., Coles, A.J., Clark, A., Gilmore, S. (2011). Cost-sensitive concurrent planning under duration uncertainty for service-level agreements. In Proc. of ICAPS’11 (pp. 34–41).

Corzilius, F., Kremer, G., Junges, S., Schupp, S., Ȧbrahȧm, E. (2015). SMT-RAT: An open source c+ + toolbox for strategic and parallel SMT solving. In Proc. of SAT’15 (pp. 360–368).

Dantam, N.T., Kingston, Z.K., Chaudhuri, S., Kavraki, L.E. (2016). Incremental task and motion planning: a constraint-based approach. In Proc. of RSS’16.

Dornhege, C., Eyerich, P., Keller, T., Trüg, S, Brenner, M., Nebel, B. (2009). Semantic attachments for domain-independent planning systems. In Proc. of ICAPS’09 (pp. 114–121).

Forgy, C.L. (1982). Rete: a fast algorithm for the many pattern/many object pattern match problem. Artificial Intelligence, 19(1), 17– 37.CrossRef

Fox, M., & Long, D. (2003). PDDL2.1: An extension to PDDL for expressing temporal planning domains. J Artif Intell Res (JAIR), 20, 61–124.CrossRef

Fox, M., Long, D., Magazzeni, D. (2017). Explainable planning. arXiv:1709.10256.

Giarratano, J.C. (2007). CLIPS Reference Manuals. http://clipsrules.sf.net/OnlineDocs.html.

Hofmann, T., Niemueller, T., Claßen, J, Lakemeyer, G. (2016). Continual planning in Golog. In Proc. of AAAI’16 (pp. 3346–3353).

Ingham, M., Ragno, R., Williams, B. (2001). A reactive model-based programming language for robotic space explorers. In Proc. of i-SAIRAS’01.

Ingrand, F.F., Chatila, R., Alami, R., Robert, F. (1996). PRS: A high level supervision and control language for autonomous mobile robots. In Proc. of ICRA’96 (pp. 43–49).

Leofante, F. (2018). Guaranteed plans for multi-robot systems via Optimization Modulo Theories. In Proc. of AAAI’18.

Leofante, F., Ábrahám, E, Niemueller, T., Lakemeyer, G., Tacchella, A. (2017). On the synthesis of guaranteed-quality plans for robot fleets in logistics scenarios via optimization modulo theories. In Procof IRI’17 (pp. 403–410).

McDermott, D., Ghallab, M., Howe, A., Knoblock, C., Ram, A., Veloso, M., Weld, D., Wilkins, D. (1998). PDDL – The Planning Domain Definition Language. Tech. rep., AIPS-98 Planning Competition Committee.

Nedunuri, S., Prabhu, S., Moll, M., Chaudhuri, S., Kavraki, L.E. (2014). SMT-Based synthesis of integrated task and motion plans from plan outlines. In Proc. of ICRA’14 (pp. 655–662).

Niemueller, T., Ferrein, A., Lakemeyer, G. (2009). A Lua-based behavior engine for controlling the humanoid robot Nao. In RoboCup Symposium (p. 2009).

Niemueller, T., Lakemeyer, G., Ferrein, A. (2013). Incremental task-level reasoning in a competitive factory automation scenario. In Proc. of AAAI’13 Spring Symposium.

Niemueller, T., Lakemeyer, G., Ferrein, A. (2015). The RoboCup Logistics League as a benchmark for planning in robotics. In Proc. of PlanRob@ICAPS’15.

Niemueller, T., Karpas, E., Vaquero, T., Timmons, E. (2016a). Planning competition for logistics robots in simulation. In Proc. of PlanRob@ICAPS’16.

Niemueller, T., Neumann, T., Henke, C., Schönitz, S, Reuter, S., Ferrein, A., Jeschke, S., Lakemeyer, G. (2016b). Improvements for a robust production in the RoboCup Logistics League 2016. In Proc. of RoboCup’16 (pp. 589–600).

Niemueller, T, Lakemeyer, G, Leofante, F, Ábrahám, E. (2017). Towards CLIPS-based Task Execution and Monitoring with SMT-based Decision Optimization. In: Proc. of PlanRob@ICAPS’17.

Nieuwenhuis, R., & Oliveras, A. (2006). On SAT modulo theories and optimization problems. In Proc. of SAT’06 (pp. 156–169).

Quigley, M., Conley, K., Gerkey, B., Faust, J., Foote, T., Leibs, J., Wheeler, R., Ng, A.Y. (2009). ROS: An open-source robot operating system. In ICRA workshop on open source software, (Vol. 3 p. 5).

RCLL Technical Committee. (2017). RoboCup Logistics League – Rules and regulations 2017.

Saha, I., Ramaithitima, R., Kumar, V., Pappas, G.J., Seshia, S.A. (2014). Automated composition of motion primitives for multi-robot systems from safe LTL specifications. In Proc. of IROS’14 (pp. 1525–1532).

Sebastiani, R., & Tomasi, S. (2015). Optimization modulo theories with linear rational costs. ACM Transactions on Computational Logic, 16(2), 12:1–12:43.CrossRef

Sebastiani, R., & Trentin, P. (2015a). OptimathSAT: A tool for optimization modulo theories. In Proc. of CAV’15 (pp. 447–454).

Sebastiani, R., & Trentin, P. (2015b). Pushing the envelope of optimization modulo theories with linear-arithmetic cost functions. In Proc. of TACAS’15 (pp. 335–349).

Verma, V., Estlin, T., Jónsson, A., Pasareanu, C., Simmons, R., Tso, K. (2005a). Plan execution interchange language (PLEXIL) for executable plans and command sequences. In Proc. of i-SAIRAS’05.

Verma, V., Jónsson, A., Simmons, R., Estlin, T., Levinson, R. (2005b). Survey of command execution systems for NASA spacecraft and robots. In Plan execution: a reality check, workshop at ICAPS’05.

Verma, V., Jónsson, A., Pasareanu, C., Iatauro, M. (2006). Universal executive and PLEXIL: Engine and language for robust spacecraft control and operations. In American institute of aeronautics and astronautics space.

Wang, Y., Dantam, N.T., Chaudhuri, S., Kavraki, L.E. (2016). Task and motion policy synthesis as liveness games. In Proc. of ICAPS’16 (p. 536).

Wygant, R.M. (1989). CLIPS: A powerful development and delivery expert system tool. Computers & Industrial Engineering, 17, 1–4.CrossRef

Zwilling, F., Niemueller, T., Lakemeyer, G. (2014). Simulation for the RoboCup Logistics League with real-world environment agency and multi-level abstraction. In Robot Soccer World Cup (pp. 220–232). Springer.

Title: Integrated Synthesis and Execution of Optimal Plans for Multi-Robot Systems in Logistics
Authors: Francesco Leofante
Erika Ábrahám
Tim Niemueller
Gerhard Lakemeyer
Armando Tacchella
Publication date: 19-05-2018
Publisher: Springer US
Published in: Information Systems Frontiers / Issue 1/2019
Print ISSN: 1387-3326
Electronic ISSN: 1572-9419
DOI: https://doi.org/10.1007/s10796-018-9858-3

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"

Springer Professional "Wirtschaft"

Other articles of this Issue 1/2019

An information integration and transmission model of multi-source data for product quality and safety

Schema Extraction for Deep Web Query Interfaces Using Heuristics Rules

Exploiting Repositories in Mobile Software Ecosystems from a Governance Perspective

Towards a Reuse Strategic Decision Pattern Framework – from Theories to Practices

Towards a Methodology for Knowledge Reuse Based on Semantic Repositories

Quantitative Analysis of Apache Storm Applications: The NewsAsset Case Study

Premium Partner