|
|
Foundations of Robotics
Seminar, May 9, 2007
Time
and Place | Seminar Abstract | Speaker
Appointments
Efficient Incremental
Search with State Dominance
G. Ayorkor Mills-Tettey
NSH 1507
Refreshments 4:15 pm
Talk 4:30 pm
Incremental search techniques are useful when changes
can occur in a search graph, such as when re-planning paths for mobile robots
in partially known environments. Dominance
relationships are used to prune graphs in search algorithms, thus speeding up
search problems in large state spaces. While
algorithms 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. Building on D* Lite,
this talk presents DD* Lite, an incremental search
algorithm that supports reasoning about state dominance, thus resulting in
significant improvements in search efficiency in large state spaces with
dominance.
For appointments, please contact G. Ayorkor
Mills-Tettey.
The Robotics Institute is part of the School of Computer Science, Carnegie Mellon University.