Loading...
Please wait, while we are loading the content...
Similar Documents
DD* Lite: Efficient incremental search with state dominance (2006)
| Content Provider | CiteSeerX |
|---|---|
| Author | Dias, M. Bernardine Stentz, Anthony Mills-Tettey, G. Ayorkor |
| Abstract | This paper presents DD * Lite, an efficient incremental search algorithm for problems that can capitalize on state domi-nance. Dominance relationships between nodes are used to prune graphs in search algorithms. Thus, exploiting state dominance relationships can considerably speed up search problems in large state spaces, such as mobile robot path planning considering uncertainty, time, or energy constraints. Incremental search techniques are useful when changes can occur in the search graph, such as when re-planning paths for mobile robots in partially known environments. While algo-rithms such as D * and D * Lite are very efficient incremental search algorithms, they cannot be applied as formulated to search problems in which state dominance is used to prune the graph. DD * Lite extends D * Lite to seamlessly support reasoning about state dominance. It maintains the algorith-mic simplicity and incremental search capability of D * Lite, while resulting in orders of magnitude increase in search effi-ciency in large state spaces with dominance. We illustrate the efficiency of DD * Lite with simulation results from apply-ing the algorithm to a path planning problem with time and energy constraints. We also prove that DD * Lite is sound, complete, optimal, and efficient. |
| File Format | |
| Publisher Date | 2006-01-01 |
| Access Restriction | Open |
| Subject Keyword | Mobile Robot Incremental Search Capability Efficient Incremental Search Search Graph Path Planning Problem Algorith-mic Simplicity State Dominance Relationship Dominance Relationship Search Problem State Dominance State Domi-nance Incremental Search Technique Mobile Robot Path Efficient Incremental Search Algorithm Magnitude Increase Re-planning Path Search Effi-ciency Large State Space Simulation Result Search Algorithm Dd Lite Energy Constraint |
| Content Type | Text |
| Resource Type | Article |
