publication . Preprint . 2018

Static and Dynamic Path Planning Using Incremental Heuristic Search

Khattab, Asem;
Open Access English
  • Published: 19 Apr 2018
Abstract
Path planning is an important component in any highly automated vehicle system. In this report, the general problem of path planning is considered first in partially known static environments where only static obstacles are present but the layout of the environment is changing as the agent acquires new information. Attention is then given to the problem of path planning in dynamic environments where there are moving obstacles in addition to the static ones. Specifically, a 2D car-like agent traversing in a 2D environment was considered. It was found that the traditional configuration-time space approach is unsuitable for producing trajectories consistent with th...
Subjects
free text keywords: Computer Science - Robotics
Download from

1 Introduction 1 1.1 Concepts and Terminology . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Problem De nition and Modeling . . . . . . . . . . . . . . . . . . . . 5 1.3.1 Planning in a Static Environment . . . . . . . . . . . . . . . 6 1.3.2 Planning in a Dynamic Environment . . . . . . . . . . . . . . 7

2 Planning in Partially-Known Static Environments 8 2.1 Heuristic-Based Path Planning Algorithms . . . . . . . . . . . . . . . 8 2.1.1 Backward A* . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.1.2 Dynamic Replanning (D*) . . . . . . . . . . . . . . . . . . . . 12 2.1.3 Anytime Planning (ARA*) . . . . . . . . . . . . . . . . . . . 14 2.1.4 Anytime Dynamic Replanning (AD*) . . . . . . . . . . . . . 16 2.2 Test Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2.1 Forming a Grid . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2.2 Search Algorithms and Search Information . . . . . . . . . . 19 2.2.3 Heuristic and Connectivity Functions . . . . . . . . . . . . . 21 2.2.4 Graphing and Animation . . . . . . . . . . . . . . . . . . . . 22 2.3 Results and Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.3.1 Behavior Tests . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.3.2 Performance Tests . . . . . . . . . . . . . . . . . . . . . . . . 34 2.3.3 Insights on the Performance of AD* . . . . . . . . . . . . . . 36

3 Planning in Dynamic Environments 39 3.1 Dynamic Constraints in Incremental Search . . . . . . . . . . . . . . 40 3.2 A Proposed E cient Planning . . . . . . . . . . . . . . . . . . . . . . 42 3.2.1 Graph Formation and Position Discretization . . . . . . . . . 43 3.2.2 Collision Checking and Speed Discretization . . . . . . . . . . 48 3.3 Simulation Environment . . . . . . . . . . . . . . . . . . . . . . . . . 57 3.4 Results and Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.4.1 C++ Implementation and Tests . . . . . . . . . . . . . . . . 60 3.4.2 MATLAB Simulation Results . . . . . . . . . . . . . . . . . . 63 [1] Thrun, S. (2010) \Toward robotic cars." Communications of the ACM.

[11] Hart, P. E.; Nilsson, N. J.; Raphael, B. (1968). \A Formal Basis for the Heuristic Determination of Minimum Cost Paths". IEEE Transactions on Systems Science and Cybernetics SSC4.

[12] Russell, S.; and Norvig, P. (2010). \Arti cial Intelligence, A Modern Approach". Prentice-Hall.

[14] Likhachev, M.; Gordon, G.; Thrun, S. (2003). \ARA*: Anytime A* with provable bounds on sub-optimality". Advances in Neural Information Processing Systems. MIT Press.

[15] Likhachev, M.; Ferguson, D.; Gordon, G.; Stentz, A.; Thrun, S. (2005). \Anytime Dynamic A*: An Anytime, Replanning Algorithm". Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS).

Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue