Time-constrained graph searches


These projects aim at developing algorithms that are capable of searching very large graphs in real-time and come with rigorous theoretical guarantees on performance.

Here are some of the classes of graph searches I am interested in:

  • Anytime graph searches designed to operate under constraints on planning time. For example, ARA* (NIPS '03).
  • Incremental graph searches for dealing with graphs that change over time. For example, LPA* (NIPS '02), D* Lite (Transactions on Robotics and Automation '05), Real-Time Adaptive A* (AAMAS '06).
  • Anytime incremental graph searches for planning both under time constraints and when graph changes over time. For example, Anytime D* (Artificial Intelligence Journal '08).
  • Randomized graph searches for planning in high-dimensional spaces with provable bounds on sub-optimality. For example, R* (AAAI '08).