{"id":251552,"date":"2013-07-10T18:46:01","date_gmt":"2013-07-11T01:46:01","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/?post_type=msr-research-item&#038;p=251552"},"modified":"2023-11-13T08:27:25","modified_gmt":"2023-11-13T16:27:25","slug":"gauss-meets-canadian-traveler-shortest-path-problems-correlated-natural-dynamics","status":"publish","type":"msr-research-item","link":"https:\/\/www.microsoft.com\/en-us\/research\/publication\/gauss-meets-canadian-traveler-shortest-path-problems-correlated-natural-dynamics\/","title":{"rendered":"Gauss Meets Canadian Traveler: Shortest-Path Problems with Correlated Natural Dynamics"},"content":{"rendered":"<div class=\"pubdetails\">\n<div>In a variety of real world problems from robot navigation\u00a0to logistics, agents face the challenge of path optimization\u00a0on a graph with unknown edge costs. These settings can\u00a0be generally formalized as the Canadian Traveler Problems\u00a0(CTPs). Although in many applications the edge costs\u00a0have dependencies resulting from world dynamics, CTPs\u00a0with such structure have received considerably less attention than those with independent edge costs, largely because\u00a0the dependence structure is often problem-specific and difficult to state compactly. Yet, in a wide variety of navigation\u00a0tasks, spatial correlations between edge traversal costs are\u00a0governed by natural phenomena such as winds, congestion,\u00a0or ocean currents, which are conveniently described with a\u00a0well-understood machine learning model | Gaussian Process (GP). In this article, we propose a synthesis of CTPs\u00a0and GPs, the Gaussian Traveler Problem (GTP). In GTPs,\u00a0an agent observes the costs of graph edges when traversing them, and uses the observed costs to adjust its belief\u00a0over other edges via Gaussian Process updates. Examples\u00a0of GTP instances include aircraft, trac, and vessel navigation, to name just a few. Computing optimal agent behavior\u00a0for a GTP turns out to be equivalent to solving a Partially\u00a0Observable MDP with continuous observation space. We\u00a0present an approximate algorithm for solving GTPs with\u00a0efficient machine-learning and decision-making components,\u00a0whose design is in influenced by the challenges of real-world\u00a0problems. Despite the intractability of computing an optimal policy, our experiments in the aircraft navigation scenario with real wind data demonstrate that our framework can significantly improve upon state-of-the-art techniques\u00a0for planning airplane routes.<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p>In a variety of real world problems from robot navigation\u00a0to logistics, agents face the challenge of path optimization\u00a0on a graph with unknown edge costs. These settings can\u00a0be generally formalized as the Canadian Traveler Problems\u00a0(CTPs). Although in many applications the edge costs\u00a0have dependencies resulting from world dynamics, CTPs\u00a0with such structure have received considerably less attention than [&hellip;]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"footnotes":""},"msr-content-type":[3],"msr-research-highlight":[],"research-area":[13556,13562],"msr-publication-type":[193716],"msr-product-type":[],"msr-focus-area":[],"msr-platform":[],"msr-download-source":[],"msr-locale":[268875],"msr-field-of-study":[],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-251552","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-artificial-intelligence","msr-research-area-computer-vision","msr-locale-en_us"],"msr_publishername":"AAMAS","msr_edition":"","msr_affiliation":"","msr_published_date":"2014-5-5","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"","msr_chapter":"","msr_isbn":"","msr_journal":"","msr_volume":"","msr_number":"","msr_editors":"","msr_series":"","msr_issue":"","msr_organization":"","msr_how_published":"","msr_notes":"","msr_highlight_text":"","msr_release_tracker_id":"","msr_original_fields_of_study":"","msr_download_urls":"","msr_external_url":"","msr_secondary_video_url":"","msr_longbiography":"","msr_microsoftintellectualproperty":1,"msr_main_download":"332093","msr_publicationurl":"","msr_doi":"","msr_publication_uploader":[{"type":"file","viewUrl":"https:\/\/www.microsoft.com\/en-us\/research\/wp-content\/uploads\/2013\/07\/AAMAS2014.pdf","id":"332093","title":"aamas2014","label_id":"243109","label":0}],"msr_related_uploader":"","msr_attachments":[],"msr-author-ordering":[{"type":"user_nicename","value":"Debadeepta Dey","user_id":31594,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=Debadeepta Dey"},{"type":"user_nicename","value":"Andrey Kolobov","user_id":30910,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=Andrey Kolobov"},{"type":"user_nicename","value":"Rich Caruana","user_id":33365,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=Rich Caruana"},{"type":"user_nicename","value":"Ece Kamar","user_id":31710,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=Ece Kamar"},{"type":"user_nicename","value":"Eric Horvitz","user_id":32033,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=Eric Horvitz"},{"type":"user_nicename","value":"Ashish Kapoor","user_id":30903,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=Ashish Kapoor"}],"msr_impact_theme":[],"msr_research_lab":[],"msr_event":[],"msr_group":[237595],"msr_project":[256167],"publication":[],"video":[],"download":[],"msr_publication_type":"inproceedings","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/251552"}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":1,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/251552\/revisions"}],"predecessor-version":[{"id":393467,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/251552\/revisions\/393467"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=251552"}],"wp:term":[{"taxonomy":"msr-content-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-content-type?post=251552"},{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=251552"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=251552"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=251552"},{"taxonomy":"msr-product-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-product-type?post=251552"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=251552"},{"taxonomy":"msr-platform","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-platform?post=251552"},{"taxonomy":"msr-download-source","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-download-source?post=251552"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=251552"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=251552"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=251552"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=251552"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=251552"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=251552"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}