Optimal multi-modal journey planning under uncertainty is a challenging problem, due in part to an increased branching factor generated by nondeterministic actions. Deterministic search, which ignores all uncertainty, can be much faster, but deterministic plans lack correctness and optimality guarantees in the uncertainty-aware domain.
We present a novel approach that combines the strengths of both deterministic and nondeterministic search in order to achieve superior performance. Initially, an A* search is used checking whether the resulting deterministic plan remains correct and optimal under uncertainty. When the plan is invalid, a backpropagation step through the A*'s search graph improves the initial heuristic while preserving its admissibility. After the backpropagation, an AO* search is run with the new improved heuristic. A theoretical analysis proves that our approach is sound and optimal. Our backpropagation correctly handles a subtle issue arising in the presence of state-dominance pruning. This supports the use of these two powerful speedup techniques in combination, for a better overall performance.
We empirically evaluate our solution in multi-modal journey planning under uncertainty, with realistic data from three European cities. Our results show that our approach brings a significant performance improvement over a state-of-the-art, highly optimized journey planning engine based on AO* search.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 firstname.lastname@example.org
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 email@example.com