Static and Dynamic Path Planning Using Incremental Heuristic Search

Preprint English OPEN
Khattab, Asem (2018)
  • Subject: Computer Science - Robotics

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 the dynamic constraints of a car. A novel scheme is then suggested where the state space is 4D consisting of position, speed and time but the search is done in the 3D space composed by position and speed. Simulation tests shows that the new scheme is capable of efficiently producing trajectories respecting the dynamic constraint of a car-like agent with a bound on their optimality.
  • References (7)

    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).

  • Metrics
    No metrics available
Share - Bookmark