This is an example of AD* (Anytime Dynamic A*) Path Planning algorithm with a moving agent. Note that the search is going backwards. Click and drag on the grid to set up obstacles. Then you may change the maximum number of expansions during one step. After you set up an environment and the number of expansions, type your decrement value, for how AD* decreases ε, or use the default value and hit Move to move the agent. Every time it moves, it senses obstacles around it. Note that the agent can see obstacles only in eight cells around it. If the agent finds that the next state on its path is an obstacle, it resets ε value and recomputes the path. Otherwise, it decreases ε value and moves one step ahead. Initial ε value can also be changed. Just type in a new value and hit Start Over. To reset the environment, hit Reset.
Notation:
- expanded state
- unknown obstacle
- obstacle
- empty cell which is known to the robot as an obstacle
12.2
- v value (cost from the goal to the current state)
