{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T10:13:25Z","timestamp":1772705605230,"version":"3.50.1"},"reference-count":41,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Decision Analysis"],"published-print":{"date-parts":[[2026,3]]},"abstract":"<jats:p>This research considers Bayesian decision-analytic approaches toward the traversal of an uncertain graph. Namely, a traveler progresses over a graph in which rewards are gained upon a node\u2019s first visit, and costs are incurred for every edge traversal. The traveler knows the graph\u2019s adjacency matrix and the starting position but does not know the rewards and costs. The traveler is a Bayesian who encodes his beliefs about these values using a Gaussian process prior and who seeks to maximize his expected utility over these beliefs. Adopting a decision-analytic perspective, we develop sequential decision-making solution strategies for this coupled information-collection and network-routing problem. We show that the problem is NP-hard and derive properties of the optimal walk. These properties provide heuristics for the traveler\u2019s problem that balance exploration and exploitation. We provide a practical case study focused on the use of unmanned aerial systems for public safety and empirically study policy performance in myriad Erd\u00f6s\u2013R\u00e9nyi settings.<\/jats:p>\n                  <jats:p>Funding: This work was supported by the Office of Naval Research [Grant 6000012277] and the Air Force Office of Scientific Research [Grant 21RT0867].<\/jats:p>","DOI":"10.1287\/deca.2024.0239","type":"journal-article","created":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T12:42:13Z","timestamp":1759322533000},"page":"11-27","source":"Crossref","is-referenced-by-count":0,"title":["Bayesian Graph Traversal"],"prefix":"10.1287","volume":"23","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8432-4680","authenticated-orcid":false,"given":"William N.","family":"Caballero","sequence":"first","affiliation":[{"name":"Department of Operational Sciences, Air Force Institute of Technology, WPAFB, Ohio 45433"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2425-9151","authenticated-orcid":false,"given":"Phillip R.","family":"Jenkins","sequence":"additional","affiliation":[{"name":"Department of Operational Sciences, Air Force Institute of Technology, WPAFB, Ohio 45433"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2376-0710","authenticated-orcid":false,"given":"David","family":"Banks","sequence":"additional","affiliation":[{"name":"Department of Statistical Sciences, Duke University, Durham, North Carolina 27708"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1718-6839","authenticated-orcid":false,"given":"Matthew","family":"Robbins","sequence":"additional","affiliation":[{"name":"Department of Operational Sciences, Air Force Institute of Technology, WPAFB, Ohio 45433"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2015.0668"},{"key":"B2","unstructured":"Al-Kanj L, Powell WB, Bouzaiene-Ayari B (2023) The information-collecting vehicle routing problem: Stochastic optimization for emergency storm response. Preprint, submitted January 16, https:\/\/arxiv.org\/abs\/2301.06497."},{"key":"B3","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177700276"},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1040.0124"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1287\/deca.2015.0325"},{"key":"B6","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2013.1164"},{"issue":"1","key":"B7","first-page":"1","volume":"9","author":"Buhmann MD","year":"2000","journal-title":"Acta Numerics"},{"key":"B8","first-page":"28350","volume-title":"Advances in Neural Information Processing Systems","volume":"34","author":"Cohen A","year":"2021"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1214\/21-AOAS1451"},{"key":"B10","unstructured":"Frazier PI (2018a) A tutorial on Bayesian optimization. Preprint, submitted July 8, https:\/\/arxiv.org\/abs\/1807.02811."},{"key":"B11","doi-asserted-by":"publisher","DOI":"10.1287\/educ.2018.0188"},{"key":"B12","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1080.0314"},{"issue":"2","key":"B13","first-page":"937","volume":"32","author":"Gardner JR","year":"2014","journal-title":"Proc. 31st Internat. Conf. Machine Learn."},{"key":"B14","doi-asserted-by":"publisher","DOI":"10.1017\/9781108348973"},{"key":"B15","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2013.0476"},{"key":"B16","doi-asserted-by":"publisher","DOI":"10.1137\/0216026"},{"key":"B17","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2020.05.007"},{"key":"B18","unstructured":"International Association of Chiefs of Police (2020) Small unmanned aircraft systems. Accessed May 16, 2025, https:\/\/www.theiacp.org\/sites\/default\/files\/2020-06\/Unmanned%20Aircraft%20FULL%20-%2006222020.pdf."},{"key":"B19","unstructured":"International Association of Fire Chiefs (2024) UAS tactics. Accessed May 16, 2025, https:\/\/www.iafc.org\/topics-and-tools\/communications-technology\/uas-toolkit\/uas-resource\/uas-tactics."},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523689"},{"key":"B21","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2023.0196"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1287\/deca.1050.0044"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-021-10012-x"},{"key":"B24","first-page":"15584","volume-title":"Proc. 39th Internat. Conf. Machine Learn.","author":"Min Y","year":"2022"},{"key":"B25","unstructured":"National Urban Security Technology Laboratory (2024) Blue unmanned aircraft systems for first responders. Accessed May 16, 2025, https:\/\/www.dhs.gov\/sites\/default\/files\/2024-03\/24_03_1_st_blueuasfocusgroupreport.pdf."},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780198805090.001.0001"},{"key":"B27","first-page":"969","volume-title":"Proc. 23rd AAAI Conf. Artificial Intelligence","author":"Nikolova E","year":"2008"},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2018.07.014"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1002\/9781119815068"},{"key":"B30","first-page":"141","volume-title":"Handbooks Oper. Res. Management Sci.","volume":"8","author":"Powell WB","year":"1995"},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1100.0873"},{"key":"B32","doi-asserted-by":"publisher","DOI":"10.1137\/12086279X"},{"key":"B33","doi-asserted-by":"publisher","DOI":"10.1287\/opre.49.5.796.10608"},{"key":"B34","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2015.2494218"},{"key":"B35","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-019-00378-1"},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2021.07.014"},{"key":"B37","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2017.2738664"},{"key":"B38","doi-asserted-by":"publisher","DOI":"10.1287\/deca.2020.0421"},{"key":"B39","volume-title":"Operations Research: An Introduction","author":"Taha HA","year":"2013"},{"key":"B40","unstructured":"Thul L, Powell WB (2023) An information-collecting drone management problem for wildfire mitigation. Preprint, submitted January 17, https:\/\/arxiv.org\/abs\/2301.07013."},{"key":"B41","doi-asserted-by":"crossref","unstructured":"Zhang C, Hartline JD, Dimoulas C (2022) Karp: A language for NP reductions.\n                      Proc. 43rd ACM SIGPLAN Internat. Conf. Programming Language Design Implementation\n                      (Association for Computing Machinery, New York), 762\u2013776.","DOI":"10.1145\/3519939.3523732"}],"container-title":["Decision Analysis"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/deca.2024.0239","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T09:20:08Z","timestamp":1772702408000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/deca.2024.0239"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["10.1287\/deca.2024.0239"],"URL":"https:\/\/doi.org\/10.1287\/deca.2024.0239","relation":{},"ISSN":["1545-8490","1545-8504"],"issn-type":[{"value":"1545-8490","type":"print"},{"value":"1545-8504","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3]]}}}