Accelerated A* path planning

ABSTRACT

The paper addresses the area of path planning for non-holonomic vehicles operating in a large-scale dynamic continuous three-dimensional space where the vehicle has to avoid given obstacles and restricted areas. For vehicles, motion dynamics is defined by means of constraints on the driving manoeuvres and restrictions on smoothness of the trajectory. The paper addresses only the basic spatial path planning problem -- a process searching for a spatial arrangement of the trajectory from the given start position and orientation to the given target position and orientation. Extended problems like incremental planning are not considered by this paper. The dynamic environment means that obstacles' and restricted areas' definitions are altered almost after each particular search.

REFERENCES

• 1: A. Botea, M. Müller, and J. Schaeffer. Near optimal hierarchical path-finding. Journal of Game Development, 1(1):7--28, 2004.
• 2: S. Carpin and G. Pillonetto. Merging the adaptive random walks planner with the randomized potential field planner. In Proceedings of IEEE International Workshop on Robot Motion and Control, pages 151--156, 2005.
• 3: S. Carpin and G. Pillonetto. Robot motion planning using adaptive random walks. IEEE Transactions on Robotics&Automation, 21(1):129--136, 2005.
• 4: J. Carsten, D. Ferguson, and A. Stentz. 3D Field D*: Improved Path Planning and Replanning in Three Dimensions. In Proceedings of the 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 3381--3386, 2006.
• 5: D. C. C. Conner, A. A. Rizzi, and H. Choset. Composition of local potential functions for global robot control and navigation. In Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems, 2003.
• 6: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 7: P. Hart, N. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, (2):100--107, 1968.
• 8: S. M. La Valle and J. J. Kuffner. Rapidly exploring random trees: Progress and prospects. In B. R. Donald, K. M. Lynch, and D. Rus, editors, Algorithmic and Computational Robitics: New Directions, pages 293--308, MA, USA, 2001. A K Peters, Wellesley.
• 9: Steven M. LaValle, Planning Algorithms, Cambridge University Press, New York, NY, 2006
• 10: S. R. Lindemann and S. M. La Valle. Smoothly blending vector fields for global robot navigation. In Proceedings of IEEE Conference Decision&Control, 2005.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Graph and tree search strategies

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Intelligent agents
      I.2.9 Robotics
          Subjects: Autonomous vehicles

General Terms:
Algorithms, Experimentation, Performance

Keywords:
A*, adaptive sampling, autonomous vehicle, motion planning, path planning