Informative Path Planning with Limited Adaptivity

References

• Agarwal A, Assadi S, Khanna S (2019) Stochastic submodular cover with limited adaptivity. Chan TM, ed. Proc. 30th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 323–342. Google Scholar
• Agarwal A, Ghuge R, Nagarajan V (2022) Batched dueling bandits. Chaudhuri K, Jegelka S, Song L, Szepesvári C, Niu G, Sabato S, eds. Proc. 39th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 162 (JMLR.org), 89–110.Google Scholar
• Asadpour A, Nazerzadeh H (2016) Maximizing stochastic monotone submodular functions. Management Sci. 62(8):2374–2391.Link, Google Scholar
• Balkanski E, Singer Y (2018) Approximation guarantees for adaptive sampling. Dy J, Krause A, eds. Proc. 35th Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 80 (JMLR.org), 393–402.Google Scholar
• Balkanski E, Breuer A, Singer Y (2018) Non-monotone submodular maximization in exponentially fewer iterations. Bengio S, Wallach H, Larochelle H, Grauman K, Cesa-Bianchi N, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 31 (Curran Associates, Red Hook, NY), 2359–2370.Google Scholar
• Balkanski E, Rubinstein A, Singer Y (2019) An exponential speedup in parallel running time for submodular maximization without loss in approximation. Chan TM, ed. Proc. 30th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 283–302.Google Scholar
• Călinescu G, Zelikovsky A (2005) The polymatroid Steiner problems. J. Combin. Optim. 9(3):281–294.Crossref, Google Scholar
• Charikar M, Chekuri C, Goel A, Guha S (1998) Rounding via trees: Deterministic approximation algorithms for group Steiner trees and k-median. Vitter JS, ed. Proc. 30th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 114–123.Google Scholar
• Chekuri C, Pál M (2005) A recursive greedy algorithm for walks in directed graphs. Proc. 46th Annual IEEE Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 245–253.Google Scholar
• Chekuri C, Quanrud K (2019) Parallelizing greedy for submodular set function maximization in matroids and beyond. Charikar M, Cohen E, eds. Proc. 51st Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 78–89.Google Scholar
• Cui Y, Nagarajan V (2023) Minimum cost adaptive submodular cover. Kavitha T, Mehlhorn K, eds. 2023 Sympos. Simplicity Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 12–27.Google Scholar
• Esfandiari H, Karbasi A, Mirrokni V (2021a) Adaptivity in adaptive submodularity. Belkin M, Kpotufe S, eds. Proc. 34th Conf. Learn. Theory, Proceedings of Machine Learning Research, vol. 134 (JMLR.org), 1823–1846.Google Scholar
• Esfandiari H, Karbasi A, Mehrabian A, Mirrokni V (2021b) Regret bounds for batched bandits. Proc. AAAI Conf. Artificial Intelligence 35(8):7340–7348.Crossref, Google Scholar
• Gao Z, Han Y, Ren Z, Zhou Z (2019) Batched multi-armed bandits problem. Wallach H, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox E, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 32 (Curran Associates, Red Hook, NY), 501–511.Google Scholar
• Garg N, Konjevod G, Ravi R (2000) A polylogarithmic approximation algorithm for the group Steiner tree problem. J. Algorithms 37(1):66–84.Crossref, Google Scholar
• Ghuge R, Gupta A, Nagarajan V (2024) The power of adaptivity for stochastic submodular cover. Oper. Res. 72(3):1156–1176.Link, Google Scholar
• Glock K, Meyer A (2023) Spatial coverage in routing and path planning problems. Eur. J. Oper. Res. 305(1):1–20.Crossref, Google Scholar
• Golovin D, Krause A (2011) Adaptive submodularity: Theory and applications in active learning and stochastic optimization. J. Artificial Intelligence Res. 42:427–486. Google Scholar
• Grammel N, Hellerstein L, Kletenik D, Lin P (2017) Scenario submodular cover. Jansen K, Mastrolilli M, eds. Approximation and Online Algorithms (Springer, Cham, Switzerland), 116–128.Crossref, Google Scholar
• Gupta A, Nagarajan V, Ravi R (2017a) Approximation algorithms for optimal decision trees and adaptive TSP problems. Math. Oper. Res. 42(3):876–896.Link, Google Scholar
• Gupta A, Nagarajan V, Singla S (2017b) Adaptivity gaps for stochastic probing: Submodular and XOS functions. Klein PN, ed. Proc. 28th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1688–1702.Google Scholar
• Halperin E, Krauthgamer R (2003) Polylogarithmic inapproximability. Larmore LL, Goemans MX, eds. ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 585–594.Google Scholar
• Hollinger GA, Mitra U, Sukhatme GS (2017) Active classification: Theory and application to underwater inspection. Christensen H, Khatib O, eds. Robotics Res. (Springer, Cham, Switzerland), 95–110.Google Scholar
• Hollinger GA, Singh S, Djugash J, Kehagias A (2009) Efficient multi-robot search for a moving target. Internat. J. Robotics Res. 28(2):201–219.Crossref, Google Scholar
• Hollinger GA, Englot B, Hover FS, Mitra U, Sukhatme GS (2013) Active planning for underwater inspection and the benefit of adaptivity. Internat. J. Robotics Res. 32(1):3–18.Crossref, Google Scholar
• Im S, Nagarajan V, van der Zwaan R (2016) Minimum latency submodular cover. ACM Trans. Algorithms 13(1):13:1–13:28. Google Scholar
• Krause A, Guestrin C (2005) Near-optimal nonmyopic value of information in graphical models. Proc 21st Conf. Uncertainty Artificial Intelligence (AUAI Press, Arlington, VA), 324–331.Google Scholar
• Li F, Cheng D, Hadjieleftheriou M, Kollios G, Teng SH (2005) On trip planning queries in spatial databases. Bauzer Medeiros C, Egenhofer MJ, Bertino E, eds. Advances in Spatial and Temporal Databases, Lecture Notes in Computer Science, vol. 3633 (Springer, Berlin), 273–290.Crossref, Google Scholar
• Lim ZW, Hsu D, Lee WS (2015) Adaptive stochastic optimization: From sets to paths. Cortes C, Lawrence N, Lee D, Sugiyama M, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 28 (Curran Associates, Red Hook, NY), 1585–1593.Google Scholar
• Lim ZW, Hsu D, Lee WS (2016) Adaptive informative path planning in metric spaces. Internat. J. Robotics Res. 35(5):585–598.Crossref, Google Scholar
• Navidi F, Kambadur P, Nagarajan V (2020) Adaptive submodular ranking and routing. Oper. Res. 68(3):856–877.Link, Google Scholar
• Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions—I. Math. Programming 14(1):265–294. Crossref, Google Scholar
• Singh A, Krause A, Kaiser WJ (2009a) Nonmyopic adaptive informative path planning for multiple robots. Proc. 21st Internat. Joint Conf. Artificial Intelligence (Morgan Kaufmann Publishers Inc., San Francisco), 1843–1850.Google Scholar
• Singh A, Krause A, Guestrin C, Kaiser WJ (2009b) Efficient informative sensing using multiple robots. J. Artificial Intelligence Res. 34(1):707–755.Crossref, Google Scholar
• Sukhatme GS, Dhariwal A, Zhang B, Oberg C, Stauffer B, Caron DA (2007) Design and development of a wireless robotic networked aquatic microbial observing system. Environ. Engrg. Sci. 24(2):205–215. Google Scholar
• Tan R, Ghuge R, Nagarajan V (2024) Informative path planning with limited adaptivity. Dasgupta S, Mandt S, Li Y, eds. Proc. 27th Internat. Conf. Artificial Intelligence Statist., Proceedings of Machine Learning Research, vol. 238 (JMLR.org), 4006–4014.Google Scholar
• Tan R, Ghuge R, Nagarajan V (2026) Informative path planning with limited adaptivity. https://doi.org/10.1287/ijoc.2024.0893.cd, https://github.com/INFORMSJoC/2024.0893.Google Scholar
• Wolsey L (1982) An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2(4):385–393.Crossref, Google Scholar
• Zhang H, Vorobeychik Y (2016) Submodular optimization with routing constraints. Schuurmans D, Wellman MP, eds. Proc. 30th AAAI Conf. Artificial Intelligence (AAAI Press, Washington, DC), 819–826.Google Scholar