Gauss Meets Canadian Traveler: Shortest-Path Problems with Correlated Natural Dynamics

Debadeepta Dey, Andrey Kolobov, Rich Caruana, Ece Kamar, Eric Horvitz, and Ashish Kapoor
Autonomous Agents and Multi-Agent Systems (AAMAS), March, 2014.


Download
  • Adobe portable document format (pdf) (5MB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract
In a variety of real world problems from robot navigation to logistics, agents face the challenge of path optimization on a graph with unknown edge costs. These settings can be generally formalized as the Canadian Traveler Problems (CTPs) [?]. Although in many applications the edge costs have dependencies resulting from world dynamics, CTPs with such structure have received considerably less atten- tion than those with independent edge costs, largely because the dependence structure is often problem-speci c and di- cult to state compactly. Yet, in a wide variety of navigation tasks, spatial correlations between edge traversal costs are governed by natural phenomena such as winds, congestion, or ocean currents, which are conveniently described with a well-understood machine learning model | Gaussian Pro- cess (GP). In this article, we propose a synthesis of CTPs and GPs, the Gaussian Traveler Problem (GTP). In GTPs, an agent observes the costs of graph edges when travers- ing them, and uses the observed costs to adjust its belief over other edges via Gaussian Process updates. Examples of GTP instances include aircraft, trac, and vessel naviga- tion, to name just a few. Computing optimal agent behavior for a GTP turns out to be equivalent to solving a Partially Observable MDP with continuous observation space. We present an approximate algorithm for solving GTPs with ecient machine-learning and decision-making components, whose design is in uenced by the challenges of real-world problems. Despite the intractability of computing an opti- mal policy, our experiments in the aircraft navigation sce- nario with real wind data demonstrate that our framework can signi cantly improve upon state-of-the-art techniques for planning airplane routes.

Notes

Text Reference
Debadeepta Dey, Andrey Kolobov, Rich Caruana, Ece Kamar, Eric Horvitz, and Ashish Kapoor, "Gauss Meets Canadian Traveler: Shortest-Path Problems with Correlated Natural Dynamics," Autonomous Agents and Multi-Agent Systems (AAMAS), March, 2014.

BibTeX Reference
@inproceedings{Dey_2014_7583,
   author = "Debadeepta Dey and Andrey Kolobov and Rich Caruana and Ece Kamar and Eric Horvitz and Ashish Kapoor",
   title = "Gauss Meets Canadian Traveler: Shortest-Path Problems with Correlated Natural Dynamics",
   booktitle = "Autonomous Agents and Multi-Agent Systems (AAMAS)",
   month = "March",
   year = "2014",
}