{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,19]],"date-time":"2025-12-19T09:58:50Z","timestamp":1766138330151,"version":"3.38.0"},"reference-count":71,"publisher":"SAGE Publications","issue":"4-5","license":[{"start":{"date-parts":[[2024,5,16]],"date-time":"2024-05-16T00:00:00Z","timestamp":1715817600000},"content-version":"vor","delay-in-days":411,"URL":"http:\/\/www.sagepub.com\/licence-information-for-chorus"}],"funder":[{"name":"Amazon"},{"DOI":"10.13039\/501100001677","name":"Institut National de la Sant\u00e9 et de la Recherche M\u00e9dicale","doi-asserted-by":"publisher","award":["#R01EB019335"],"award-info":[{"award-number":["#R01EB019335"]}],"id":[{"id":"10.13039\/501100001677","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100016680","name":"Toyota Research Institute, North America","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100016680","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100019201","name":"Honda Research Institute","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100019201","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["#1544797"],"award-info":[{"award-number":["#1544797"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["#1637748"],"award-info":[{"award-number":["#1637748"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1750489"],"award-info":[{"award-number":["IIS-1750489"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2023,4]]},"abstract":"<jats:p> We address the problem of robot motion planning under uncertainty where the only observations are through contact with the environment. Such problems are typically solved by planning optimistically assuming unknown space is free, moving along the planned path and re-planning if the robot collides. However this approach can be very inefficient, leading to many unnecessary collisions and unproductive motion. We propose a new formulation, the Blindfolded Traveler\u2019s Problem (BTP), for planning on a graph containing edges with unknown validity, with true validity observed only through attempted traversal by the robot. The solution to a BTP is a policy indicating the next edge to attempt given previous observations and an initial belief. We prove that BTP is NP-complete and show that exact modeling of the belief is intractable, therefore we present several approximation-based policies and beliefs. For the policy we propose graph search with edge weights augmented by the probability of collision. For the belief representation we propose a weighted Mixture of Experts of Collision Hypothesis Sets and a Manifold Particle Filter. Empirical evaluation in simulation and on a real robot arm shows that our proposed approach vastly outperforms several baselines as well as a previous approach that does not employ the BTP framework. <\/jats:p>","DOI":"10.1177\/02783649231170893","type":"journal-article","created":{"date-parts":[[2023,5,17]],"date-time":"2023-05-17T02:48:11Z","timestamp":1684291691000},"page":"289-309","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":1,"title":["The blindfolded traveler\u2019s problem: A search framework for motion planning with contact estimates"],"prefix":"10.1177","volume":"42","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9765-0258","authenticated-orcid":false,"given":"Brad","family":"Saund","sequence":"first","affiliation":[{"name":"Robotics, Univeristy of Michigan, Ann Arbor, MI, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2762-8888","authenticated-orcid":false,"given":"Sanjiban","family":"Choudhury","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA, USA"}]},{"given":"Siddhartha","family":"Srinivasa","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA, USA"}]},{"given":"Dmitry","family":"Berenson","sequence":"additional","affiliation":[{"name":"Robotics, Univeristy of Michigan, Ann Arbor, MI, USA"}]}],"member":"179","published-online":{"date-parts":[[2023,5,16]]},"reference":[{"volume-title":"Appearing in Proceedings of the 16th International Con-ference on Artificial Intelligence and Statistics (AISTATS)2013","year":"2013","author":"Agrawal S","key":"bibr1-02783649231170893"},{"key":"bibr2-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007367"},{"volume-title":"A Robotic System for Reaching in Dense Clutter that Integrates Model Predictive Control, Learning, Haptic Mapping, and Planning","year":"2014","author":"Bhattacharjee T","key":"bibr3-02783649231170893"},{"volume-title":"Canadian Traveler Problem with Remote Sensing","year":"2009","author":"Bnaya Z","key":"bibr4-02783649231170893"},{"key":"bibr5-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.844107"},{"key":"bibr6-02783649231170893","volume":"3","author":"Brafman RI","year":"2002","journal-title":"Journal of Machine Learning Research"},{"key":"bibr7-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2012.01.001"},{"volume-title":"An Empirical Evaluation of Thompson Sampling","year":"2011","author":"Chapelle O","key":"bibr8-02783649231170893"},{"key":"bibr9-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v29i1.9694"},{"key":"bibr10-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2016.7759551"},{"volume-title":"Advances in Neural Information Processing Systems","year":"2017","author":"Choudhury S","key":"bibr11-02783649231170893"},{"key":"bibr12-02783649231170893","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2018\/679"},{"key":"bibr13-02783649231170893","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2014.X.033"},{"key":"bibr14-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1609\/icaps.v26i1.13788"},{"key":"bibr15-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1239\/jap\/1032192861"},{"volume-title":"High-Quality Policies for the Canadian Traveler\u2019s Problem","year":"2010","author":"Eyerich P.","key":"bibr16-02783649231170893"},{"volume-title":"Field D*: An Interpolation-Based Path Planner and Replanner","year":"2007","author":"Ferguson D","key":"bibr17-02783649231170893"},{"volume-title":"Complexity of Canadian Traveler Problem Variants Theoretical Computer Science","year":"2013","author":"Fried D","key":"bibr18-02783649231170893"},{"key":"bibr19-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1145\/1273496.1273531"},{"volume-title":"Near-optimal bayesian active learning with noisy observations","year":"2010","author":"Golovin D","key":"bibr20-02783649231170893"},{"volume-title":"Efficient bayes-adaptive reinforcement learning using sample-based search advances in neural information processing systems","year":"2012","author":"Guez A.","key":"bibr21-02783649231170893"},{"key":"bibr22-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2019.8793782"},{"key":"bibr23-02783649231170893","volume":"8","author":"Gy\u00f6rgy A","year":"2007","journal-title":"Journal of Machine Learning Research"},{"key":"bibr24-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2017.2723903"},{"key":"bibr25-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1609\/icaps.v28i1.13879"},{"key":"bibr26-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2015.7139603"},{"key":"bibr27-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2014.6943148"},{"key":"bibr28-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA40945.2020.9197014"},{"volume-title":"Safe Motion Planning in Unknown Environments: Optimality Benchmarks and Tractable Policies","year":"2018","author":"Janson L","key":"bibr29-02783649231170893"},{"key":"bibr30-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"volume-title":"Belief-Space Planning Using Learned Models with Application to Underactuated Hands","year":"2019","author":"Kimmel A","key":"bibr31-02783649231170893"},{"volume-title":"The Manifold Particle Filter for State Estimation on High-Dimensional Implicit Manifolds","year":"2016","author":"Klingensmith M","key":"bibr32-02783649231170893"},{"volume-title":"Bandit Based Monte-Carlo Planning European Conference on Machine Learning","year":"2006","author":"Kocsis L","key":"bibr33-02783649231170893"},{"volume-title":"D* Lite","year":"2002","author":"Koenig S","key":"bibr34-02783649231170893"},{"key":"bibr35-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2011.5980463"},{"key":"bibr36-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1109\/IROS45743.2020.9341534"},{"volume-title":"Constructing Optimal Binary Decision Trees Is Np-Complete Information processing Letters","year":"1976","author":"Laurent H","key":"bibr37-02783649231170893"},{"key":"bibr38-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2013.6697176"},{"volume-title":"Adaptive Stochastic Optimization: From Sets to Paths Advances in Neural Information Processing Systems","year":"2015","author":"Lim ZW","key":"bibr39-02783649231170893"},{"key":"bibr40-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915596378"},{"volume-title":"Shortest Path under Uncertainty: Exploration Versus Exploitation","year":"2017","author":"Lim ZW","key":"bibr41-02783649231170893"},{"key":"bibr42-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1016\/B978-1-55860-377-6.50052-9"},{"volume-title":"Generalized Lazy Search for Robot Motion Planning: Interleaving Search and Edge Evaluation via Event-Based Toggles","year":"2019","author":"Mandalika A","key":"bibr43-02783649231170893"},{"key":"bibr44-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1609\/icaps.v28i1.13931"},{"key":"bibr45-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2018.8461163"},{"key":"bibr46-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1609\/icaps.v27i1.13860"},{"volume-title":"Route Planning under Uncertainty: The Canadian Traveller Problem","year":"2008","author":"Nikolova E","key":"bibr47-02783649231170893"},{"key":"bibr48-02783649231170893","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/8727.003.0027"},{"volume-title":"Efficient Reinforcement Learning via Posterior Sampling","year":"2013","author":"Osband I","key":"bibr49-02783649231170893"},{"key":"bibr50-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA48506.2021.9561761"},{"volume-title":"Shortest Paths without a Map Theoretical Computer Science","year":"1991","author":"Papadimitriou CH","key":"bibr51-02783649231170893"},{"journal-title":"Humanoids","year":"2014","author":"Park D","key":"bibr52-02783649231170893"},{"key":"bibr53-02783649231170893","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2010.VI.037"},{"key":"bibr54-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2018.8594365"},{"volume-title":"Bayesian Learning for Safe High-Speed Navigation in Unknown Environments","year":"2015","author":"Richter C.","key":"bibr55-02783649231170893"},{"volume-title":"Introduction to Stochastic Dynamic Programming","year":"2014","author":"Ross S.","key":"bibr56-02783649231170893"},{"key":"bibr57-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1561\/9781680834710"},{"volume-title":"Motion Planning for Manipulators in Unknown Environments with Contact Sensing Uncertainty","year":"2018","author":"Saund B.","key":"bibr58-02783649231170893"},{"volume-title":"The Blindfolded Robot: A Bayesian Approach to Planning with Contact Feedback","year":"2019","author":"Saund B.","key":"bibr59-02783649231170893"},{"key":"bibr60-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1108\/01439919810240234"},{"key":"bibr61-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1038\/nature16961"},{"volume-title":"Monte-Carlo Planning in Large POMDPs","year":"2010","author":"Silver D.","key":"bibr62-02783649231170893"},{"key":"bibr63-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1994.351061"},{"key":"bibr64-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2017.2747409"},{"volume-title":"On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples","year":"1933","author":"Thompson WR","key":"bibr65-02783649231170893"},{"volume-title":"Probabilistic Robotics (Intelligent Robotics and Autonomous Agents)","year":"2005","author":"Thrun S","key":"bibr66-02783649231170893"},{"key":"bibr67-02783649231170893","volume":"2","author":"Tong S","year":"2001","journal-title":"Journal of Machine Learning Research"},{"key":"bibr68-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1163\/156855308X314533"},{"key":"bibr69-02783649231170893","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2019.8793572"},{"volume-title":"Probabilistic Planning via Determinization in Hindsight","year":"2008","author":"Yoon SW","key":"bibr70-02783649231170893"},{"key":"bibr71-02783649231170893","doi-asserted-by":"publisher","DOI":"10.3390\/s17122762"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649231170893","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/02783649231170893","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649231170893","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649231170893","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T22:54:52Z","timestamp":1740869692000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/02783649231170893"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,4]]},"references-count":71,"journal-issue":{"issue":"4-5","published-print":{"date-parts":[[2023,4]]}},"alternative-id":["10.1177\/02783649231170893"],"URL":"https:\/\/doi.org\/10.1177\/02783649231170893","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"type":"print","value":"0278-3649"},{"type":"electronic","value":"1741-3176"}],"subject":[],"published":{"date-parts":[[2023,4]]}}}