{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T12:36:44Z","timestamp":1740141404654,"version":"3.37.3"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,9,14]],"date-time":"2024-09-14T00:00:00Z","timestamp":1726272000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,9,14]],"date-time":"2024-09-14T00:00:00Z","timestamp":1726272000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["2023 ONR Summer Faculty Fellowship"],"award-info":[{"award-number":["2023 ONR Summer Faculty Fellowship"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Intell Robot Syst"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Some human-machine systems are designed so that machines (robots) gather and deliver data to remotely located operators (humans) through an interface to aid them in classification. The performance of a human as a (binary) classifier-in-the-loop is characterized by probabilities of correctly classifying objects (or points of interest) as a true target or a false target. These two probabilities depend on the time spent collecting information at a point of interest (POI), known as dwell time. The information gain associated with collecting information at a POI is then a function of dwell time and discounted by the revisit time, i.e., the duration between consecutive revisits to the same POI, to ensure that the vehicle covers all POIs in a timely manner. The objective of the routing problem for classification is to route the vehicles optimally, which is a discrete problem, and determine the optimal dwell time at each POI, which is a continuous optimization problem, to maximize the total discounted information gain while visiting every POI at least once. Due to the coupled discrete and continuous problem, which makes the problem hard to solve, we make a simplifying assumption that the information gain is discounted exponentially by the revisit time; this assumption enables one to decouple the problem of routing with the problem of determining optimal dwell time at each POI for a single vehicle problem. For the multi-vehicle problem, since the problem involves task partitioning between vehicles in addition to routing and dwell time computation, we provide a fast heuristic to obtain high-quality feasible solutions.<\/jats:p>","DOI":"10.1007\/s10846-024-02169-1","type":"journal-article","created":{"date-parts":[[2024,9,14]],"date-time":"2024-09-14T08:02:47Z","timestamp":1726300967000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["UAV Routing for Enhancing the Performance of a Classifier-in-the-loop"],"prefix":"10.1007","volume":"110","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6446-2077","authenticated-orcid":false,"given":"Deepak Prakash","family":"Kumar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-4933-5204","authenticated-orcid":false,"given":"Pranav","family":"Rajbhandari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Loy","family":"McGuire","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8377-0657","authenticated-orcid":false,"given":"Swaroop","family":"Darbha","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Donald","family":"Sofge","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,9,14]]},"reference":[{"issue":"4","key":"2169_CR1","doi-asserted-by":"publisher","first-page":"2047","DOI":"10.1109\/TCYB.2020.3008248","volume":"52","author":"S Ji","year":"2022","unstructured":"Ji, S., Zhang, Z., Ying, S., Wang, L., Zhao, X., Gao, Y.: Kullback-leibler divergence metric learning. IEEE Transactions on Cybernetics. 52(4), 2047\u20132058 (2022). https:\/\/doi.org\/10.1109\/TCYB.2020.3008248","journal-title":"IEEE Transactions on Cybernetics."},{"issue":"5","key":"2169_CR2","doi-asserted-by":"publisher","first-page":"696","DOI":"10.1002\/rob.21542","volume":"32","author":"G Pandey","year":"2015","unstructured":"Pandey, G., McBride, J.R., Savarese, S., Eustice, R.M.: Automatic extrinsic calibration of vision and lidar by maximizing mutual information. J. Field Robot. 32(5), 696\u2013722 (2015). https:\/\/doi.org\/10.1002\/rob.21542","journal-title":"J. Field Robot."},{"issue":"11","key":"2169_CR3","doi-asserted-by":"publisher","first-page":"1097","DOI":"10.1016\/S0305-0548(97)00031-2","volume":"24","author":"N Mladenovi\u0107","year":"1997","unstructured":"Mladenovi\u0107, N., Hansen, P.: Variable neighborhood search. Comput. Oper. Res. 24(11), 1097\u20131100 (1997). https:\/\/doi.org\/10.1016\/S0305-0548(97)00031-2","journal-title":"Comput. Oper. Res."},{"issue":"9","key":"2169_CR4","doi-asserted-by":"publisher","first-page":"1430","DOI":"10.1057\/jors.2014.108","volume":"66","author":"X Wang","year":"2015","unstructured":"Wang, X., Golden, B., Wasil, E.: The min-max multi-depot vehicle routing problem: heuristics and computational results. J. Oper. Res. Soc. 66(9), 1430\u20131441 (2015). https:\/\/doi.org\/10.1057\/jors.2014.108","journal-title":"J. Oper. Res. Soc."},{"key":"2169_CR5","unstructured":"Applegate, D.L., Bixby, R.E., Chv\u00e1tal, V., Cook, W.J.: The Traveling Salesman Problem: A Computational Study, Princeton University Press (2007)"},{"key":"2169_CR6","doi-asserted-by":"crossref","unstructured":"Gutin, G., Punnen, A.P.: The Traveling Salesman Problem and Its Variations, Springer (2007)","DOI":"10.1007\/b101971"},{"issue":"6","key":"2169_CR7","doi-asserted-by":"publisher","first-page":"747","DOI":"10.1016\/j.orl.2007.02.001","volume":"35","author":"W Malik","year":"2007","unstructured":"Malik, W., Rathinam, S., Darbha, S.: An approximation algorithm for a symmetric generalized multiple depot, multiple travelling salesman problem. Oper. Res. Lett. 35(6), 747\u2013753 (2007). https:\/\/doi.org\/10.1016\/j.orl.2007.02.001","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"2169_CR8","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1109\/MRA.2010.938844","volume":"17","author":"P Oberlin","year":"2010","unstructured":"Oberlin, P., Rathinam, S., Darbha, S.: Today\u2019s traveling salesman problem. IEEE Robotics & Automation Magazine. 17(4), 70\u201377 (2010). https:\/\/doi.org\/10.1109\/MRA.2010.938844","journal-title":"IEEE Robotics & Automation Magazine."},{"key":"2169_CR9","doi-asserted-by":"publisher","unstructured":"Oberlin, P., Rathinam, S., Darbha, S.: A transformation for a multiple depot, multiple traveling salesman problem. In: 2009 American Control Conference, pp. 2636\u20132641 (2009). https:\/\/doi.org\/10.1109\/ACC.2009.5160665","DOI":"10.1109\/ACC.2009.5160665"},{"key":"2169_CR10","unstructured":"Helsgaun, K.: LKH TSP solver (2023). http:\/\/webhotel4.ruc.dk\/~keld\/research\/LKH\/"},{"issue":"1","key":"2169_CR11","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1109\/TASE.2006.872110","volume":"4","author":"S Rathinam","year":"2007","unstructured":"Rathinam, S., Sengupta, R., Darbha, S.: A resource allocation algorithm for multivehicle systems with motion constraints. IEEE Trans. Autom. Sci. Eng. 4(1), 98\u2013104 (2007)","journal-title":"IEEE Trans. Autom. Sci. Eng."},{"key":"2169_CR12","doi-asserted-by":"publisher","unstructured":"Manyam, S.G., Rathinam, S., Darbha, S.: Computation of lower bounds for a multiple depot, multiple vehicle routing problem with motion constraints. Journal of Dynamic Systems, Measurement, and Control. 137(9) (2015). https:\/\/doi.org\/10.1115\/1.4030354","DOI":"10.1115\/1.4030354"},{"key":"2169_CR13","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1007\/s10846-016-0459-4","volume":"88","author":"SG Manyam","year":"2017","unstructured":"Manyam, S.G., Rathinam, S., Casbeer, D., Garcia, E.: Tightly bounding the shortest dubins paths through a sequence of points. J. Intell. Robot. Syst. 88, 495\u2013511 (2017). https:\/\/doi.org\/10.1007\/s10846-016-0459-4","journal-title":"J. Intell. Robot. Syst."},{"key":"2169_CR14","doi-asserted-by":"publisher","unstructured":"Dubins, L.E.: On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. Am. J. Math. 79 (1957). https:\/\/doi.org\/10.2307\/2372560","DOI":"10.2307\/2372560"},{"issue":"2","key":"2169_CR15","doi-asserted-by":"publisher","first-page":"550","DOI":"10.1109\/TRO.2020.3032171","volume":"37","author":"SKK Hari","year":"2021","unstructured":"Hari, S.K.K., Rathinam, S., Darbha, S., Kalyanam, K., Manyam, S.G., Casbeer, D.: Optimal uav route planning for persistent monitoring missions. IEEE Trans. Rob. 37(2), 550\u2013566 (2021). https:\/\/doi.org\/10.1109\/TRO.2020.3032171","journal-title":"IEEE Trans. Rob."},{"key":"2169_CR16","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2022.3210784","author":"SKK Hari","year":"2022","unstructured":"Hari, S.K.K., Rathinam, S., Darbha, S., Manyam, S.G., Kalyanam, K., Casbeer, D.: Bounds on optimal revisit times in persistent monitoring missions with a distinct and remote service station. IEEE Trans. Rob. (2022). https:\/\/doi.org\/10.1109\/TRO.2022.3210784","journal-title":"IEEE Trans. Rob."},{"key":"2169_CR17","doi-asserted-by":"publisher","unstructured":"Hari, S.K.K., Rathinam, S., Darbha, S., Casbeer, D.W.: Cooperative Coverage with a Leader and a Wingmate in Communication-Constrained Environments (2022). https:\/\/doi.org\/10.48550\/arXiv.2210.02628","DOI":"10.48550\/arXiv.2210.02628"},{"key":"2169_CR18","doi-asserted-by":"publisher","unstructured":"Bhadoriya, A.S., Montez, C.M., Rathinam, S., Darbha, S., Casbeer, D.W., Manyam, S.G.: Optimal path planning for a convoy-support vehicle pair through a repairable network. IEEE Trans. Autom. Sci. Eng. 1\u201312 (2023) https:\/\/doi.org\/10.1109\/TASE.2023.3305392","DOI":"10.1109\/TASE.2023.3305392"},{"issue":"4","key":"2169_CR19","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1109\/THMS.2016.2519603","volume":"46","author":"K Kalyanam","year":"2016","unstructured":"Kalyanam, K., Pachter, M., Patzek, M., Rothwell, C., Darbha, S.: Optimal human-machine teaming for a sequential inspection operation. IEEE Trans. Hum.-Mach. Syst. 46(4), 557\u2013568 (2016). https:\/\/doi.org\/10.1109\/THMS.2016.2519603","journal-title":"IEEE Trans. Hum.-Mach. Syst."},{"key":"2169_CR20","doi-asserted-by":"crossref","unstructured":"Cover, T.M., Thomas, J.A.: Elements of Information Theory, Wiley (2006)","DOI":"10.1002\/047174882X"},{"key":"2169_CR21","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/s10489-008-0136-9","volume":"32","author":"C-Y Lee","year":"2010","unstructured":"Lee, C.-Y., Lee, Z.-J., Lin, S.-W., Ying, K.-C.: An enhanced ant colony optimization (eaco) applied to capacitated vehicle routing problem. Appl. Intell. 32, 88\u201395 (2010). https:\/\/doi.org\/10.1007\/s10489-008-0136-9","journal-title":"Appl. Intell."},{"issue":"1","key":"2169_CR22","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1109\/TRO.2011.2166435","volume":"28","author":"NE Du Toit","year":"2011","unstructured":"Du Toit, N.E., Burdick, J.W.: Robot motion planning in dynamic, uncertain environments. IEEE Trans. Rob. 28(1), 101\u2013115 (2011). https:\/\/doi.org\/10.1109\/TRO.2011.2166435","journal-title":"IEEE Trans. Rob."},{"key":"2169_CR23","doi-asserted-by":"publisher","unstructured":"Kaufman, E., Lee, T., Ai, Z.: Autonomous exploration by expected information gain from probabilistic occupancy grid mapping. In: 2016 IEEE International Conference on Simulation, Modeling, and Programming for Autonomous Robots (SIMPAR), IEEE, pp. 246\u2013251 (2016). https:\/\/doi.org\/10.1109\/SIMPAR.2016.7862403","DOI":"10.1109\/SIMPAR.2016.7862403"},{"key":"2169_CR24","doi-asserted-by":"publisher","unstructured":"Zaenker, T., R\u00fcckin, J., Menon, R., Popovi\u0107, M., Bennewitz, M.: Graph-based view motion planning for fruit detection. arXiv preprint arXiv:2303.03048. (2023) https:\/\/doi.org\/10.48550\/arXiv.2303.03048","DOI":"10.48550\/arXiv.2303.03048"},{"key":"2169_CR25","doi-asserted-by":"publisher","unstructured":"Paull, L., Saeedi, S., Li, H., Myers, V.: An information gain based adaptive path planning method for an autonomous underwater vehicle using sidescan sonar. In: 2010 IEEE International Conference on Automation Science and Engineering, IEEE, pp. 835\u2013840 (2010). https:\/\/doi.org\/10.1109\/COASE.2010.5584478","DOI":"10.1109\/COASE.2010.5584478"},{"key":"2169_CR26","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1007\/s10846-009-9335-9","volume":"56","author":"Y Mostofi","year":"2009","unstructured":"Mostofi, Y.: Decentralized communication-aware motion planning in mobile networks: an information-gain approach. J. Intell. Rob. Syst. 56, 233\u2013256 (2009). https:\/\/doi.org\/10.1007\/s10846-009-9335-9","journal-title":"J. Intell. Rob. Syst."},{"key":"2169_CR27","unstructured":"Novakovic, J.: Using information gain attribute evaluation to classify sonar targets. In: 17th Telecommunications Forum TELFOR, pp. 1351\u20131354 (2009). Citeseer"},{"key":"2169_CR28","doi-asserted-by":"publisher","unstructured":"Deng, D., Duan, R., Liu, J., Sheng, K., Shimada, K.: Robotic exploration of unknown 2d environment using a frontier-based automatic-differentiable information gain measure. In: 2020 IEEE\/ASME International Conference on Advanced Intelligent Mechatronics (AIM), IEEE, pp. 1497\u20131503 (2020). https:\/\/doi.org\/10.1109\/AIM43001.2020.9158881","DOI":"10.1109\/AIM43001.2020.9158881"},{"issue":"10","key":"2169_CR29","doi-asserted-by":"publisher","first-page":"1375","DOI":"10.1177\/0278364914526288","volume":"33","author":"BJ Julian","year":"2014","unstructured":"Julian, B.J., Karaman, S., Rus, D.: On mutual information-based control of range sensing robots for mapping applications. The International Journal of Robotics Research. 33(10), 1375\u20131392 (2014). https:\/\/doi.org\/10.1177\/0278364914526288","journal-title":"The International Journal of Robotics Research."},{"key":"2169_CR30","doi-asserted-by":"publisher","unstructured":"Bai, S., Wang, J., Chen, F., Englot, B.: Information-theoretic exploration with bayesian optimization. In: 2016 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), IEEE, pp. 1816\u20131822 (2016). https:\/\/doi.org\/10.1109\/IROS.2016.7759289","DOI":"10.1109\/IROS.2016.7759289"},{"issue":"5","key":"2169_CR31","doi-asserted-by":"publisher","first-page":"684","DOI":"10.1016\/j.robot.2009.11.005","volume":"58","author":"F Amigoni","year":"2010","unstructured":"Amigoni, F., Caglioti, V.: An information-based exploration strategy for environment mapping with mobile robots. Robot. Auton. Syst. 58(5), 684\u2013699 (2010). https:\/\/doi.org\/10.1016\/j.robot.2009.11.005","journal-title":"Robot. Auton. Syst."},{"key":"2169_CR32","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/s10514-011-9249-9","volume":"31","author":"N Basilico","year":"2011","unstructured":"Basilico, N., Amigoni, F.: Exploration strategies based on multi-criteria decision making for searching environments in rescue operations. Auton. Robot. 31, 401\u2013417 (2011). https:\/\/doi.org\/10.1007\/s10514-011-9249-9","journal-title":"Auton. Robot."},{"key":"2169_CR33","unstructured":"Alipour, M., Faez, K.: On design of mobile agent routing algorithm for information gain maximization in wireless sensor networks. In: International Conference on Systems and Networks Communications (2011)"},{"key":"2169_CR34","doi-asserted-by":"publisher","unstructured":"Montez, C., Darbha, S., Valicka, C., Staid, A.: Routing of an unmanned vehicle for classification. In: Pham, T., Solomon, L., Rainey, K. (eds.) Artificial Intelligence And Machine Learning For Multi-domain Operations Applications II, vol. 11413, p. 1141319 (2020). https:\/\/doi.org\/10.1117\/12.2558748","DOI":"10.1117\/12.2558748"},{"key":"2169_CR35","unstructured":"Kumar, S.: On maximizing the total information gain in a vehicle routing problem. Master\u2019s thesis, Texas A &M University (2023)"},{"issue":"1","key":"2169_CR36","first-page":"141","volume":"6","author":"J Carlsson","year":"2012","unstructured":"Carlsson, J., Ge, D., Subramaniam, A., Wu, A., Ye, Y.: Min-max multi-depot vehicle routing problem. Lect. Global Optim. 6(1), 141\u2013152 (2012)","journal-title":"Lect. Global Optim."},{"key":"2169_CR37","unstructured":"Gurobi Optimization, LLC: Gurobi Optimizer Reference Manual (2023). https:\/\/www.gurobi.com"},{"key":"2169_CR38","unstructured":"Reinelt, G.: TSPLIB. Accessed 22 May 2023 (1995). http:\/\/comopt.ifi.uni-heidelberg.de\/software\/TSPLIB95\/"},{"issue":"3","key":"2169_CR39","doi-asserted-by":"publisher","first-page":"1055","DOI":"10.1016\/j.ejor.2022.11.010","volume":"307","author":"P He","year":"2023","unstructured":"He, P., Hao, J.-K.: Memetic search for the minmax multiple traveling salesman problem with single and multiple depots. Eur. J. Oper. Res. 307(3), 1055\u20131070 (2023). https:\/\/doi.org\/10.1016\/j.ejor.2022.11.010","journal-title":"Eur. J. Oper. Res."},{"key":"2169_CR40","unstructured":"He, P. Accessed Sept 2023. https:\/\/github.com\/pengfeihe-angers\/minmax-mTSP"}],"container-title":["Journal of Intelligent &amp; Robotic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10846-024-02169-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10846-024-02169-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10846-024-02169-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,26]],"date-time":"2024-09-26T13:17:50Z","timestamp":1727356670000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10846-024-02169-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,14]]},"references-count":40,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2024,9]]}},"alternative-id":["2169"],"URL":"https:\/\/doi.org\/10.1007\/s10846-024-02169-1","relation":{},"ISSN":["1573-0409"],"issn-type":[{"type":"electronic","value":"1573-0409"}],"subject":[],"published":{"date-parts":[[2024,9,14]]},"assertion":[{"value":"24 February 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 August 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 September 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Preprint submission: The initial draft of the paper is available on arXiv. The DOI is  and the URL is  and the license of the preprint is arXiv.org perpetual, non-exclusive license.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}}],"article-number":"134"}}