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. G. De Giacomo, L. Iocchi, D. Nardi, and R. Rosati. Planning with sensing for a mobile robot. In Proc. of 4th European Conference on Planning (ECP'97), 1997.
4. G. DeGiacomo, Y. Lesperance, and H. J. Levesque. ConGolog, a concurrent programming language based on the situation calculus. Artificial Intelligence, 121(1-2):109--169, 2000.
5. E. H. Durfee. Distributed problem solving and planning. In G. Weiss, editor, Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence, pages 121--164. MIT Press, 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. K. Konolige. COLBERT: A language for reactive control in sapphira. Lecture Notes in Computer Science, 1303:31--50, 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. S. J. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. Pearson Education, 2003. Second Edition.
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

• Computer systems organization

  • Embedded and cyber-physical systems

    • Robotics

• Computing methodologies

  • Artificial intelligence

    • Control methods

      • Robotic planning

    • Distributed artificial intelligence

      • Multi-agent systems

    • Planning and scheduling

      • Robotic planning

  • Modeling and simulation

    • Model development and analysis

      • Modeling methodologies

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Software system models

        • Petri nets