A Petri net based approach for multi-robot path planning

详细信息    查看全文

• 作者：Marius Kloetzer (1)
  Cristian Mahulea (2)
  
• 关键词：Discrete event systems ; Abstractions ; Mobile robots ; Hybrid systems ; Algorithms
• 刊名：Discrete Event Dynamic Systems
• 出版年：2014
• 出版时间：December 2014
• 年：2014
• 卷：24
• 期：4
• 页码：417-445
• 全文大小：2,652 KB
• 参考文献：1. Belta C, Habets LCGJM (2004) Constructing decidable hybrid systems with velocity bounds. In: 43rd IEEE conference on decision and control. Paradise Island, Bahamas, pp 467鈥?72
  2. Choset H, Lynch KM, Hutchinson S, Kantor G, Burgard W, Kavraki LE, Thrun S (2005) Principles of robot motion: theory, algorithms, and implementations. MIT Press, Boston
  3. Cgal Community (2011) Cgal, Computational Geometry Algorithms Library. http://www.cgal.org
  4. Costelha H, Lima P (2012) Robot task plan representation by Petri nets: modelling, identification, analysis and execution. Journal of Autonomous Robots 33(4)337鈥?60
  5. Cowlagi RV, Tsiotras P (2010) Kinematic feasibility guarantees in geometric path planning using history-based transition costs over cell decompositions. In: American control conference (ACC), pp 5388鈥?393
  6. Cowlagi RV, Tsiotras P (2012) Hierarchical motion planning with dynamical feasibility guarantees for mobile robotic vehicles. IEEE Trans Robot 28(2):379鈥?95 CrossRef
  7. Ding J, Li E, Huang H, Tomlin CJ (2011) Reachability-based synthesis of feedback policies for motion planning under bounded disturbances. In: IEEE international conference on robotics and automation (ICRA), pp 2160鈥?165
  8. Ding XC, Smith SL, Belta C, Rus D (2011) LTL control in uncertain environments with probabilistic satisfaction guarantees. In: 18th IFAC world congress. Milan, Italy
  9. Fainekos GE, Kress-Gazit H, Pappas GJ (2005) Hybrid controllers for path planning: a temporal logic approach. In: Proceedings of the 44th IEEE conference on decision and control, pp 4885鈥?890
  10. Fukuda K (2011) CDD/CDD+ package. http://www.ifor.math.ethz.ch/~fukuda/cdd_home/
  11. Gerkey B, Mataric M (2004) A formal analysis and taxonomy of task allocation in multi-robot systems. Int J Rob Res 23(9):939鈥?54 CrossRef
  12. Habets LCGJM, Collins PJ, van Schuppen JH (2006) Reachability and control synthesis for piecewise-affine hybrid systems on simplices. IEEE Trans Autom Contr 51:938鈥?48 CrossRef
  13. Habets LCGJM, van Schuppen JH (2004) A control problem for affine dynamical systems on a full-dimensional polytope. Automatica 40:21鈥?5 CrossRef
  14. Hoffman AJ, Kruskal JB (1956) Integral boundary points of convex polyhedra. In: Kuhn HW, Tucker AW (eds) Linear inequalities and related systems. Annals of mathematics studies, vol聽38. Princeton University Press, pp 223鈥?46
  15. Jensen K (1994) Coloured Petri nets: basic concepts, analysis methods, and practical use. In: EATCS monographs on theoretical computer science. Springer
  16. Johnson B, Kress-Gazit H (2011) Probabilistic analysis of correctness of high-level robot behavior with sensor error. In: Robotics: science and systems. Los Angeles, CA
  17. Karmarkar N (1984) A new polynomial-time algorithm for linear programming. In: Proceedings of the 16th annual ACM symposium on theory of computing, STOC 鈥?4. New York, NY, USA, pp 302鈥?11
  18. Kim G, Chung W (2007) Navigation behavior selection using generalized stochastic Petri nets for a service robot. IEEE Trans Syst Man Cybern, Part C Appl Rev 37(4):494鈥?03 CrossRef
  19. King J, Pretty R, Gosine R (2003) Coordinated execution of tasks in a multiagent environment. IEEE Trans Syst Man Cybern, Part A, Syst Humans 33(5):615鈥?19 CrossRef
  20. Kloetzer M, Belta C (2010) Automatic deployment of distributed teams of robots from temporal logic motion specifications. IEEE Trans Robot 26(1):48鈥?1 CrossRef
  21. Kloetzer M, Mahulea C, Belta C, Silva M (2010) An automated framework for formal verification of timed continuous Petri nets. IEEE Trans Ind Informat 6(3):460鈥?71 CrossRef
  22. Kloetzer M, Mahulea C, Pastravanu O (2011) A probabilistic abstraction approach for planning and controlling mobile robots. In: IEEE Conf. on emerging technologies and factory automation (ETFA). Toulouse, France, pp 1鈥?
  23. Kloetzer M, Mahulea C, Pastravanu O (2011) Software tool for probabilistic abstraction for planning and controling mobile robots. http://webdiis.unizar.es/~cmahulea/research/prob_abstr.zip
  24. Konur S, Dixon C, Fisher M (2012) Analysing robot swarm behaviour via probabilistic model checking. Robot Auton Syst 60(2):199鈥?13 CrossRef
  25. Lahijanian M, Belta C, Andersson S (2009) A probabilistic approach for control of a stochastic system from LTL specifications. In: IEEE conf. on decision and control. Shanghai, China, pp 2236鈥?241
  26. LaValle SM (2006) Planning algorithms. Cambridge. http://planning.cs.uiuc.edu
  27. Little I, Thi茅baux S (2007) Probabilistic planning vs replanning. In: ICAPS workshop on IPC: past, present and future
  28. Liu W, Winfield AFT, Sa J (2007) Modelling swarm robotic systems: a case study in collective foraging. In: Towards autonomous robotic systems (TAROS), pp 25鈥?2
  29. Mahulea C, Kloetzer M (2012) A probabilistic abstraction approach for planning and controlling mobile robots. In: IEEE Conf. on emerging technologies and factory automation (ETFA). Krakow, Poland
  30. Makhorin A (2007) GLPK-GNU linear programming kit. http://www.gnu.org/software/glpk
  31. Murata T (1989) Petri nets: properties, analysis and applications. Proc IEEE 77(4):541鈥?80 CrossRef
  32. Quottrup MM, Bak T, Izadi-Zamanabadi R (2004) Multi-robot motion planning: a timed automata approach. In: IEEE conf. on robotics and automation. New Orleans, LA, pp 4417鈥?422
  33. Rippel E, Bar-Gill A, Shimkin N (2005) Fast graph-search algorithms for general-aviation flight trajectory generation. J Guid Control Dyn 28(4):801鈥?11 CrossRef
  34. Shewchuk JR (1996) Triangle: engineering a 2D quality mesh generator and delaunay triangulator. In: Lin MC, Manocha D (eds) Applied computational geometry: towards geometric engineering (Lecture Notes in Computer Science), vol 1148. Springer, pp 203鈥?22. From the First ACM Workshop on Applied Computational Geometry
  35. Silva M (1993) Introducing Petri nets. In: Practice of Petri nets in manufacturing. Chapman & Hall, pp 1鈥?2
  36. Silva M, Teruel E, Colom JM (1998) Linear algebraic and linear programming techniques for the analysis of net systems. In: Rozenberg G, Reisig W (eds) Lectures in Petri nets. I: basic models (Lecture Notes in Computer Science), vol 1491. Springer, pp 309鈥?73
  37. The MathWorks (2010) MATLAB庐 2010b. Natick, MA
  
• 作者单位：Marius Kloetzer (1)
  Cristian Mahulea (2)
  
  1. Department of Automatic Control and Applied Informatics, Technical University 鈥淕heorghe Asachi鈥?of Iasi, Iasi, Romania
  2. Arag贸n Institute of Engineering Research (I3A), University of Zaragoza, Zaragoza, Spain
  
• ISSN：1573-7594

文摘

This paper presents a procedure for creating a probabilistic finite-state model for mobile robots and for finding a sequence of controllers ensuring the highest probability for reaching some desired regions. The approach starts by using results for controlling affine systems in simpliceal partitions, and then it creates a finite-state representation with history-based probabilities on transitions. This representation is embedded into a Petri Net model with probabilistic costs on transitions, and a highest probability path to reach a set of target regions is found. An online supervising procedure updates the paths whenever a robot deviates from the intended trajectory. The proposed probabilistic framework may prove suitable for controlling mobile robots based on more complex specifications.