Petri net plans: a formal model for representation and execution of multi-robot plans

ABSTRACT

The aim of this paper is to describe a novel representation framework for high level robot and multi-robot programming, called Petri Net Plans (PNP), that allows for representing all the action features that are needed for describing complex plans in dynamic environments. We provide a sound and complete execution algorithm for PNPs based on the semantics of Petri nets. Moreover, we show that multi-robot PNPs allow for a sound and complete distributed execution algorithm, given that a reliable communication channel is provided. PNPs have been used for describing effective plans for actual robotic agents which inhabit dynamic, partially observable and unpredictable environments, and experimented in different application scenarios.

REFERENCES

• 1: Extra Material Web Page. www.dis.uniromal.it/~ziparo/pnp_extras.html.
• 2: H. Costelha and P. Lima. Modelling, analysis and execution of robotic tasks using petri nets. Intelligent Robots and Systems, 2007. IROS 2007. IEEE/RSJ International Conference on, pages 1449--1454, Oct. 29 2007-Nov. 2 2007.
• 3: Giuseppe De Giacomo , Luca Iocchi , Daniele Nardi , Riccardo Rosati, Planning with Sensing for a Mobile Robot, Proceedings of the 4th European Conference on Planning: Recent Advances in AI Planning, p.156-168, September 24-26, 1997
• 4: Giuseppe de Giacomo , Yves Lespérance , Hector J. Levesque, ConGolog, a concurrent programming language based on the situation calculus, Artificial Intelligence, v.121 n.1-2, p.109-169, Aug. 2000 [doi>10.1016/S0004-3702(00)00031-X]
• 5: Edmund H. Durfee, Distributed problem solving and planning, Multiagent systems: a modern approach to distributed artificial intelligence, MIT Press, Cambridge, MA, 1999
• 6: A. Farinelli, L. Iocchi, D. Nardi, and V. A. Ziparo. Assignment of dynamically perceived tasks by token passing in multi-robot systems. Proceedings of the IEEE, Special issue on Multi-Robot Systems, 94(7):1271--1288, 2006.
• 7: Kurt Konolige, COLBERT: A Language for Reactive Control in Sapphira, Proceedings of the 21st Annual German Conference on Artificial Intelligence: Advances in Artificial Intelligence, p.31-52, September 09-12, 1997
• 8: M. Lötzsch, J. Bach, H.-D. Burkhard, and M. Jüngel. Designing agent behavior with the extensible agent behavior specification language XABSL. In D. Polani, B. Browning, and A. Bonarini, editors, RoboCup 2003: Robot Soccer World Cup VII, volume 3020 of Lecture Notes in Artificial Intelligence, pages 114--124, Padova, Italy, 2004. Springer.
• 9: T. Murata. Petri nets: Properties, analysis and applications. Proceedings of the IEEE, 77(4):541--580, 1989.
• 10: Stuart J. Russell , Peter Norvig, Artificial Intelligence: A Modern Approach, Pearson Education, 2003
• 11: R. Scherl and H. J. Levesque. The frame problem and knowledge producing actions, pages 689--695, 1993.
• 12: W. Sheng and Q. Yang. Peer-to-peer multi-robot coordination algorithms: petri net based analysis and design. Advanced Intelligent Mechatronics. Proceedings, 2005 IEEE/ASME International Conference on, pages 1407--1412, 24--28 July 2005.
• 13: V. A. Ziparo and L. Iocchi. Petri net plans. In Proceedings of Fourth International Workshop on Modelling of Objects, Components, and Agents (MOCA), pages 267--290, Turku, Finland, 2006.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.9 Robotics

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Petri nets

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Plan execution, formation, and generation
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Management, Theory