Bayesian Graph Traversal

References

• Aksakalli V, Sahin OF, Ari I (2016) An AO* based exact algorithm for the Canadian traveler problem. INFORMS J. Comput. 28(1):96–111.Link, Google Scholar
• 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.Google Scholar
• Bagai O (1965) The distribution of the generalized variance. Ann. Math. Statist. 36(1):120–130.Crossref, Google Scholar
• Bent RW, Van Hentenryck P (2004) Scenario-based planning for partially dynamic vehicle routing with stochastic customers. Oper. Res. 52(6):977–987.Link, Google Scholar
• Borrero JS, Prokopyev OA, Sauré D (2016) Sequential shortest path interdiction with incomplete information. Decision Anal. (Oxford) 13(1):68–98.Link, Google Scholar
• Brown DB, Smith JE (2013) Optimal sequential exploration: Bandits, clairvoyants, and wildcats. Oper. Res. 61(3):644–665.Link, Google Scholar
• Buhmann MD (2000) Radial basis functions. Acta Numerics 9(1):1–38.Google Scholar
• Cohen A, Efroni Y, Mansour Y, Rosenberg A (2021) Minimax regret for stochastic shortest path. Ranzato M, Beygelzimer A, Dauphin Y, Liang PS, Vaughan JW, eds. Advances in Neural Information Processing Systems, vol. 34 (Curran Associates Inc., Red Hook, NY), 28350–28361.Google Scholar
• Fossum TO, Travelletti C, Eidsvik J, Ginsbourger D, Rajan K (2021) Learning excursion sets of vector-valued Gaussian random fields for autonomous ocean sampling. Ann. Appl. Statist. 15(2):597–618.Crossref, Google Scholar
• Frazier PI (2018a) A tutorial on Bayesian optimization. Preprint, submitted July 8, https://arxiv.org/abs/1807.02811.Google Scholar
• Frazier PI (2018b) Bayesian optimization. INFORMS TutORials in Operations Research: Recent Advances in Optimization and Modeling of Contemporary Problems (INFORMS, Catonsville, MD), 255–278.Link, Google Scholar
• Frazier P, Powell W, Dayanik S (2009) The knowledge-gradient policy for correlated normal beliefs. INFORMS J. Comput. 21(4):599–613.Link, Google Scholar
• Gardner JR, Kusner MJ, Xu ZE, Weinberger KQ, Cunningham JP (2014) Bayesian optimization with inequality constraints. Proc. 31st Internat. Conf. Machine Learn., vol. 32, no. 2 (PMLR, New York), 937–945.Google Scholar
• Garnett R (2023) Bayesian Optimization (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• Han J, Lee C, Park S (2014) A robust scenario approach for the vehicle routing problem with uncertain travel times. Transportation Sci. 48(3):373–390.Link, Google Scholar
• Horton JD (1987) A polynomial-time algorithm to find the shortest cycle basis of a graph. SIAM J. Comput. 16(2):358–366.Crossref, Google Scholar
• Hougardy S, Zaiser F, Zhong X (2020) The approximation ratio of the 2-Opt Heuristic for the metric traveling salesman problem. Oper. Res. Lett. 48(4):401–404.Crossref, Google Scholar
• 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.Google Scholar
• 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.Google Scholar
• Karger D, Motwani R, Ramkumar GD (1997) On approximating the longest path in a graph. Algorithmica 18(1):82–98.Crossref, Google Scholar
• Lagos T, Auad R, Lagos F (2025) The online shortest path problem: Learning travel times using a multiarmed bandit framework. Transportation Sci. 59(1):28–59.Link, Google Scholar
• Lim C, Bearden JN, Smith JC (2006) Sequential search with multiattribute options. Decision Anal. (Oxford) 3(1):3–15.Link, Google Scholar
• McCammon S, Hollinger GA (2021) Topological path planning for autonomous information gathering. Autonomous Robots 45(6):821–842.Crossref, Google Scholar
• Min Y, He J, Wang T, Gu Q (2022) Learning stochastic shortest path with linear function approximation. Chaudhuri K, Jegelka S, Song L, Szepesvari C, Niu G, Sabato S, eds. Proc. 39th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 162 (PMLR, New York), 15584–15629.Google Scholar
• 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.Google Scholar
• Newman M (2018) Networks, 2nd ed. (Oxford University Press, Oxford, UK).Crossref, Google Scholar
• Nikolova E, Karger DR (2008) Route planning under uncertainty: The Canadian traveller problem. Proc. 23rd AAAI Conf. Artificial Intelligence (AAAI Press, Cambridge, MA), 969–974.Google Scholar
• Powell WB (2019) A unified framework for stochastic optimization. Eur. J. Oper. Res. 275(3):795–821.Crossref, Google Scholar
• Powell WB (2022) Reinforcement Learning and Stochastic Optimization: A Unified Framework for Sequential Decisions (John Wiley & Sons, Hoboken, NJ).Crossref, Google Scholar
• Powell WB, Jaillet P, Odoni A (1995) Stochastic and dynamic networks and routing. Handbooks Oper. Res. Management Sci. 8:141–295.Google Scholar
• Ryzhov IO, Powell WB (2011) Information collection on a graph. Oper. Res. 59(1):188–201.Link, Google Scholar
• Ryzhov IO, Powell WB (2012) Information collection for linear programs with uncertain objective coefficients. SIAM J. Optim. 22(4):1344–1368.Crossref, Google Scholar
• Secomandi N (2001) A rollout policy for the vehicle routing problem with stochastic demands. Oper. Res. 49(5):796–802.Link, Google Scholar
• Shahriari B, Swersky K, Wang Z, Adams RP, de Freitas N (2016) Taking the human out of the loop: A review of Bayesian optimization. Proc. IEEE 104(1):148–175.Crossref, Google Scholar
• Shiri D, Salman FS (2019) On the randomized online strategies for the k-Canadian traveler problem. J. Combinatorial Optim. 38(1):254–267.Crossref, Google Scholar
• Soeffker N, Ulmer MW, Mattfeld DC (2022) Stochastic dynamic vehicle routing in the light of prescriptive analytics: A review. Eur. J. Oper. Res. 298(3):801–820.Crossref, Google Scholar
• Suh J, Gong J, Oh S (2017) Fast sampling-based cost-aware path planning with nonmyopic extensions using cross entropy. IEEE Trans. Robotics 33(6):1313–1326.Crossref, Google Scholar
• Summers GJ (2021) Friction and decision rules in portfolio decision analysis. Decision Anal. (Oxford) 18(2):101–120.Link, Google Scholar
• Taha HA (2013) Operations Research: An Introduction (Pearson Education India, London).Google Scholar
• Thul L, Powell WB (2023) An information-collecting drone management problem for wildfire mitigation. Preprint, submitted January 17, https://arxiv.org/abs/2301.07013.Google Scholar
• Zhang C, Hartline JD, Dimoulas C (2022) Karp: A language for NP reductions. Proc. 43rd ACM SIGPLAN Internat. Conf. Programming Language Design Implementation (Association for Computing Machinery, New York), 762–776.Google Scholar