Nothing Special   »   [go: up one dir, main page]
Skip to main content
SpringerLink
Log in

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

  • Published:
Information Systems Frontiers Aims and scope Submit manuscript

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.

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
Listing 1
Listing 2
Listing 3
Listing 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Listing 5

Similar content being viewed by others

Explore related subjects

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

Notes

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

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

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

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

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

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

  7. 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.

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

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

References

  • Á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.

    Article  Google Scholar 

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

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

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

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

    Article  Google Scholar 

  • 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.

Download references

Author information

Authors and Affiliations

  1. Theory of Hybrid Systems, RWTH Aachen University, Aachen, Germany

    Francesco Leofante & Erika Ábrahám

  2. Knowledge-Based Systems, RWTH Aachen University, Aachen, Germany

    Tim Niemueller & Gerhard Lakemeyer

  3. Università degli Studi di Genova, Genova, Italy

    Francesco Leofante & Armando Tacchella

Authors
  1. Francesco Leofante
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Erika Ábrahám
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Tim Niemueller
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Gerhard Lakemeyer
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Armando Tacchella
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Francesco Leofante.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Leofante, F., Ábrahám, E., Niemueller, T. et al. Integrated Synthesis and Execution of Optimal Plans for Multi-Robot Systems in Logistics. Inf Syst Front 21, 87–107 (2019). https://doi.org/10.1007/s10796-018-9858-3

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10796-018-9858-3

Keywords

Search

Navigation