Invited Talks
Ruzica Piskac
Yale University
TBA
Anytime and exact search for planning problems
How to explore a DP-based state transition graph with A*, CP and LS?
Many planning problems may be solved with Dynamic Programming (DP) by decomposing the problem into subproblems which are recursively solved. These decompositions induce state transition graphs which are closely related to decision diagrams, and where optimal solutions correspond to best paths in the graphs. A* is a well known algorithm which extends Djikstra's algorithm with heuristics for guiding the path search. It is exact but not anytime. In other words, it computes a best path but it does not output sub-optimal paths while computing it.
In this talk, we will provide an overview of anytime extensions of A*, which compute a sequence of paths of increasing quality. We will also show how to combine them with Local Search (LS) in order to find better paths faster and with bounding and constraint propagation, in order to prune the graph. This will be illustrated using the Travelling Salesman Problem with Time Windows (TSPTW) as a running example. We will finish by presenting an experimental comparison with state-of-the-art approaches for solving the TSPTW and the time-dependent TSPTW.
