Skip to main navigation menu Skip to main content Skip to site footer
International Journal of Robotics and Automation Technology

Articles

Vol. 7 (2020)

µ-Planner: A Robot Path Planning Approach Based on Language Measure of Unsupervised Automata

DOI
https://doi.org/10.31875/2409-9694.2020.07.5
Submitted
November 16, 2020
Published
16.11.2020

Abstract

This paper proposes a robot path planner based on language measure, m-planner. Workspace is discretized in a occupancy grid map and we model the system by considering how events, associated to robot’s motions, take it to different cells (discrete positions). The calculated language measure values corresponds to a gradient, which the robot can use reach its destination by choosing events that take it to states with higher measure values. Concepts of Lapace’s equation and harmonic functions are used to prove that our method guarantees both the existence and monotonicity of language measure. The proposed method is simple and computationally inexpensive and guarantees existence of path from any co-accessible state to the destination. Experiments considering different scenarios have been performed to validate and compare m-planner with similar methods.

References

  1. Sheldon Axler, Paul Bourdon, and Ramey Wade. Harmonic Function Theory, volume 137. Springer Science & Business Media, 2001. https://doi.org/10.1007/978-1-4757-8137-3
  2. José Gilmar Nunes Carvalho Filho, Jean-Marie Alexandre Farines, and José Eduardo Ribeiro Cury. Modeling and synthesis of controllers for multi-robot systems using game structures. In 2013 16th International Conference on Advanced Robotics (ICAR), pages 1-8. IEEE, 2013. https://doi.org/10.1109/ICAR.2013.6766560
  3. Ishanu Chattopadhyay, Anthony Cascone, and Asok Ray. Formal-language-theoretic optimal path planning for accommodation of amortized uncertainties and dynamic effects. arXiv preprint arXiv:1008.3760, 2010.
  4. Ishanu Chattopadhyay, Goutham Mallapragada, and Asok Ray. L: An intelligent path planning algorithm based on renormalized measure of probabilistic regular languages. In 2008 American Control Conference, pages 1249-1254. IEEE, 2008. https://doi.org/10.1109/ACC.2008.4586664
  5. Ishanu Chattopadhyay, Goutham Mallapragada, and Asok Ray. : a robot path planning algorithm based on renormalised measure of probabilistic regular languages. International Journal of Control, 82(5):849-867, 2009. https://doi.org/10.1080/00207170802343196
  6. Ishanu Chattopadhyay and Asok Ray. Renormalized measure of regular languages. International Journal of Control, 79(9):1107-1117, 2006. https://doi.org/10.1080/00207170600801429
  7. Ishanu Chattopadhyay and Asok Ray. Language-measuretheoretic optimal control of probabilistic finite-state systems. International Journal of Control, 80(8):1271-1290, 2007. https://doi.org/10.1080/00207170701286322
  8. Ishanu Chattopadhyay and Asok Ray. Generalization of path planning for accommodation of amortized dynamic uncertainties in plan execution. In 2009 American Control Conference, pages 2415-2420. IEEE, 2009. https://doi.org/10.1109/ACC.2009.5160367
  9. Pritthi Chattopadhyay, Devesh K Jha, Soumik Sarkar, and Asok Ray. Path planning in gps-denied environments: A collective intelligence approach. In 2015 American Control Conference (ACC), pages 3082-3087. IEEE, 2015. https://doi.org/10.1109/ACC.2015.7171806
  10. Stuart Eiffert, He Kong, Navid Pirmarzdashti, and Salah Sukkarieh. Path planning in dynamic environments using generative rnns and monte carlo tree search. In 2020 IEEE International Conference on Robotics and Automation (ICRA), pages 10263-10269. IEEE, 2020. https://doi.org/10.1109/ICRA40945.2020.9196631
  11. Raouf Fareh, Mohammed Baziyad, Tamer Rabie, and Maamar Bettayeb. Enhancing path quality of real-time path planning algorithms for mobile robots: A sequential linear paths approach. IEEE Access, 8:167090-167104, 2020. https://doi.org/10.1109/ACCESS.2020.3016525
  12. Alessandro Gasparetto, Paolo Boscariol, Albano Lanzutti, and Renato Vidoni. Path planning and trajectory planning algorithms: A general overview. Motion and operation planning of robotic systems, pages 3-27, 2015. https://doi.org/10.1007/978-3-319-14705-5_1
  13. Alejandro Hidalgo-Paniagua, Miguel A Vega-Rodrguez, Joaqun Ferruz, and Nieves Pavón. Solving the multiobjective path planning problem in mobile robotics with a firefly-based approach. Soft Computing, 21(4):949-964, 2017. https://doi.org/10.1007/s00500-015-1825-z
  14. Devesh K Jha, Pritthi Chattopadhyay, Soumik Sarkar, and Asok Ray. Path planning in gps-denied environments via collective intelligence of distributed sensor networks. International Journal of Control, 89(5):984-999, 2016. https://doi.org/10.1080/00207179.2015.1110754
  15. Devesh K Jha, Yue Li, Thomas A Wettergren, and Asok Ray. Robot path planning in uncertain environments: A languagemeasure-theoretic approach. Journal of Dynamic Systems, Measurement, and Control, 137(3):034501, 2015. https://doi.org/10.1115/1.4027876
  16. Rahul Kala, Anupam Shukla, and Ritu Tiwari. Fusion of probabilistic a* algorithm and fuzzy inference system for robotic path planning. Artificial Intelligence Review, 33(4):307-327, 2010. https://doi.org/10.1007/s10462-010-9157-y
  17. Jean-Claude Latombe. Robot motion planning, volume 124. Springer Science & Business Media, 2012.
  18. Brenan J McCarragher. Petri net modelling for robotic assembly and trajectory planning. IEEE Transactions on Industrial Electronics, 41(6):631-640, 1994. https://doi.org/10.1109/41.334580
  19. Pablo Muñoz, Mara D R-Moreno, and Bonifacio Castaño. 3dana: A path planning algorithm for surface robotics. Engineering Applications of Artificial Intelligence, 60:175-192, 2017. https://doi.org/10.1016/j.engappai.2017.02.010
  20. Asok Ray, Jinbo Fu, and Constantino Lagoa. Optimal supervisory control of finite state automata. International Journal of Control, 77(12):1083-1100, 2004. https://doi.org/10.1080/0020717042000273762
  21. Asok Ray and Shashi Phoha. Signed real measure of regular languages for discrete-event automata. International Journal of Control, 76(18):1800-1808, 2003. https://doi.org/10.1080/00207170310001635392
  22. Asok Ray and Xi Wang. Signed real measure of regular languages. In Quantitative Measure for Discrete Event Supervisory Control, pages 3-37. Springer, 2005. https://doi.org/10.1007/0-387-23903-0_1
  23. Asok Ray. Signed real measure of regular languages for discrete event supervisory control. International Journal of Control, 78(12):949-967, 2005. https://doi.org/10.1080/00207170500202447
  24. Faranak Rahimi Soofiyani, Amir Masoud Rahmani, and Mehran Mohsenzadeh. A straight moving path planner for mobile robots in static environments using cellular automata. In 2010 2nd International Conference on Computational Intelligence, Communication Systems and Networks, pages 67-71. IEEE, 2010. https://doi.org/10.1109/CICSyN.2010.28