Very fast algorithm for nonholonomic optimal path planning and replanning, generalities and details

• Autorzy: Podsędkowski L.
• Języki publikacji: EN

Abstrakty

EN

This paper presents an original method for nonholonomic mobile robot path planning. The method is based on A* searching of a graph built in a configuration space. Very good heuristic approximation of the real cost of the path accelerates path searching significantly. Due to dynamic modifications of the graph, the path replanning procedure is much faster than brute-force replanner. The paper presents general assumptions of the method, detailed algorithms of important procedures (especially the path replanning procedure) and a new form of configuration space and open list. The simulation and experimental tests on car-like robot as well as the comparisons of this method to the others are also included.

Słowa kluczowe

EN

nonholonomic robots; dynamic path planning; graph searching

• Wydawca: Polish Academy of Sciences, Committee of Automatic Control and Robotics
• Czasopismo: Archives of Control Sciences
• Rocznik: 2001
• Tom: Vol. 11, no. 1/2
• Strony: 91--117
• Opis fizyczny: Bibliogr. 24 poz., rys., wzory

Twórcy

autor

Podsędkowski L.

• Machines Tools and Production Engineering, Technical University of Łódź, Poland

Bibliografia

• [1] J. Barraquand and J.C. Latombe: On non-holonomic mobile robots and optimal maneuvering. Revue d’intelligence artificielle, 3(2), (1989), 77-103.
• [2] J. Barraquand, B. Langlois and J.C. Latombe: Numerical potential field techniques for robot path planning. IEEE Trans. Systems, Man and Cybernetics, 22(2), (1992), 224-241.
• [3] J. Barraquand And J.-C. Latombe: Nonholonomic Multibody Mobile Robots: Controllability and Motion Planning in the Presence of Obstacles. Algorithmic, 10 (1993), 121-155.
• [4] A. Bicchi, G. Casalino and C. Santilli: Planning Shortest BoundedCurvature Paths for a Class of Nonholonomic Vehicles among Obstacles. Proc. IEEE Int. Conf. on Robotics and Automation, (1995).
• [5] G. Desaulniers, F. Soumis and J-C. Laurent: A Shortest Path Algorithm for Carlike Robot in a Polygonal Environment. Int. J. Robotics Research, 17(5), (1998), 512-530.
• [6] Rao N. G. de Saussure: The visit problem: visibility graph based solution. Proc. IEEE Int. Conf. on Robotics and Automation, (1988).
• [7] P. Jacobs and J. Canny: Planning smooth paths for mobile robots. Proc. IEEE Int. Conf. on Robotics and Automation, (1989), 2-7.
• [8] S. Jun and K. A Shin: Probabilistic approach to collision-free robot path planning. Proc. IEEE Int. Conf. on Robotics and Automation (1988).
• [9] P. Kampmann and G.K. Schmidt: Multilevel motion planning for mobile robots based on a topologically structured world model. Int. Conf. on Intelligent Autonomous Systems 2, Amsterdam, The Netherlands, (1989), 241-252.
• [10] P. Konkimalla and S.M. Lavalle: Efficient Computation of Optimal Navigation Functions for Nonholonomic Planning. Proc. 1st Workshop on Robot Motion and Control, Kiekrz, Poland, (1999).
• [11] Y. Koren and J. Borenstein: Potential field methods and their inherent limitations for mobile robot navigation. Proc. IEEE Int. Conf. on Robotics and Automation, (1991).
• [12] J.C. Latombe: Robot Motion Planning. Kluwer Academic Publisher, 1991.
• [13] J.-C. Latombe: A fast Path Planner for a Car-like Indoor Mobile Robot. Proc. 9th National Conf. on Artificial Intelligence, (1991), 659-665.
• [14] J. P. Laumond, P. E. Jacobs, M. Taix and R. M. Murray: A Motion Planner for Nonholonomic Mobile Robots. IEEE Trans. on Robotics and Automation, 10(5), (1994), 577-593.
• [15] T. Lozano-Perez: Spatial Planning: A Configuration Space Algorithm. IEEE Trans. on Computers, C-32(2), (1983), 108-120.
• [16] L. Podsędkowski: Path planner for nonholonomic mobile robot with fast replanning procedure. Proc. IEEE Int. Conf. on Robotics and Automation, (1998).
• [17] L. Podsędkowski: Dynamiczne planowanie trajektorii robotów mobilnych w zmiennej przestrzeni roboczej. Zeszyty Naukowe PŁ, Rozprawy Naukowe, 809(z. 254), (1999), (in Polish).
• [18] L. Podsędkowski: Nowa forma podziału przestrzeni konfiguracyjnej przy planowaniu ruchu mobilnych robotów z ograniczeniami nieholonomicznymi. VII Krajowa Konferencja Robotyki,Lądek-Zdrój, (2001), (in Polish).
• [19] A. Stentz: Optimal and Eflicient Path Planning for Partially-Known Environments. Proc. IEEE Int. Conf. on Robotics and Automation, (1994).
• [20] A. Stentz: The Focused D Algorithm for Real-Time Replanning. Proc. Int. Joint Conf. on Artifitial Inteligence, (1995).
• [21] M. Strobel: Navigation in Partially Unknown, Narrow, Cluttered Spaces. Proc. IEEE Int. Conf. on Robotics and Automation, (1999), 29-34.
• [22] P. Svestka and H. Overmars: Motion Planning for Carlike Robots Using a Probabilistic Learning Approach. Int. J. Robotics Research, 16(2), (1997), 119- 143.
• [23] A. Zelinsky: Using Path Transforms to Guide the Search for Findpath in 2D. Int. J. Robotics Research, 13(4), (1994).
• [24] A. Zelinsky, R.A. Jarvis, J.C. Byrne And S. Yuta: Planning Paths of Complete Coverage of an Unstructured Environment by a Mobile Robot. Int. Conf. on Advanced Robotics, Tokyo, Japan, (1993).