{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T14:05:31Z","timestamp":1756994731795},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T00:00:00Z","timestamp":1557964800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T00:00:00Z","timestamp":1557964800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2019,10]]},"DOI":"10.1007\/s10878-019-00413-1","type":"journal-article","created":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T07:04:27Z","timestamp":1557990267000},"page":"808-835","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["An evolutionary approach for the target search problem in uncertain environment"],"prefix":"10.1007","volume":"38","author":[{"given":"M.","family":"Barkaoui","sequence":"first","affiliation":[]},{"given":"J.","family":"Berger","sequence":"additional","affiliation":[]},{"given":"A.","family":"Boukhtouta","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,5,16]]},"reference":[{"key":"413_CR1","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s10472-009-9121-1","volume":"52","author":"N Agmon","year":"2008","unstructured":"Agmon N, Hazon N, Kaminka GA (2008) The giving tree: constructing trees for efficient offline and online multi-robot coverage. Ann Math Artif Intell 52:143\u2013168","journal-title":"Ann Math Artif Intell"},{"key":"413_CR2","doi-asserted-by":"crossref","unstructured":"Ankenbrandt C (1991) An extension to the theory of convergence and a proof of the time complexity of genetic algorithms. In: Foundations of genetic algorithms. Morgan Kaufman, pp 53\u201368","DOI":"10.1016\/B978-0-08-050684-5.50007-0"},{"issue":"1\u20132","key":"413_CR3","first-page":"131","volume":"28","author":"M Barkaoui","year":"2008","unstructured":"Barkaoui M, Berger J, Boukhtouta A (2008) A hybrid genetic approach for the dynamic vehicle routing problem with time windows. Am J Math Manag Sci 28(1\u20132):131\u2013154","journal-title":"Am J Math Manag Sci"},{"key":"413_CR4","doi-asserted-by":"crossref","unstructured":"Barkaoui M, Berger J, Boukhtouta A (2014) An information-theoretic-based evolutionary approach for the dynamic search path planning problem. In: International conference on advanced logistics and transport (ICALT), Hammamet, Tunisia","DOI":"10.1109\/ICAdLT.2014.6864073"},{"key":"413_CR5","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1016\/j.asoc.2015.06.035","volume":"35","author":"M Barkaoui","year":"2015","unstructured":"Barkaoui M, Berger J, Boukhtouta A (2015) Customer satisfaction in dynamic vehicle routing problem with time windows. J Appl Soft Comput 35:423\u2013432","journal-title":"J Appl Soft Comput"},{"key":"413_CR6","doi-asserted-by":"publisher","DOI":"10.1109\/WD.2016.7461521","volume-title":"Path planning of unmanned aerial vehicles with terrestrial wireless network tracking","author":"M Bekhti","year":"2016","unstructured":"Bekhti M, Abdennebi M, Achir N, Boussetta K (2016) Path planning of unmanned aerial vehicles with terrestrial wireless network tracking. Wireless days, Toulouse"},{"key":"413_CR7","unstructured":"Berger J, Happe J, Gagne C, Lau M (2009) Co-evolutionary information gathering for a cooperative unmanned aerial vehicle team. In: 12th International conference on information fusion, FUSION \u201809"},{"issue":"2","key":"413_CR8","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/s10479-016-2145-0","volume":"244","author":"J Berger","year":"2016","unstructured":"Berger J, Lo N, Barkaoui M (2016) Static target search path planning optimization with heterogeneous agents. Ann Oper Res 244(2):295\u2013312","journal-title":"Ann Oper Res"},{"issue":"1","key":"413_CR9","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/s12293-012-0076-0","volume":"4","author":"J Botzheim","year":"2012","unstructured":"Botzheim J, Toda Y, Kubota N (2012) Bacterial memetic algorithm for offline path planning of mobile robots. Memetic Computing 4(1):73\u201386","journal-title":"Memetic Computing"},{"key":"413_CR10","unstructured":"Bourgault F, Furukawa T, Durrant-Whyte HF (2003) Optimal search for a lost target in a bayesian world. In: Proceedings of the 4th international conference on field and service robotics (FSR\u201903), 24, Lake Yamanaka, Japan, pp 209\u2013222"},{"key":"413_CR11","first-page":"48","volume":"1","author":"F Bourgault","year":"2003","unstructured":"Bourgault F, Furukawa T, Durrant-Whyte HF (2003b) Coordinated decentralized search for a lost target in a Bayesian world. IEEE\/RSJ Int Conf Intell Robots Syst 1:48\u201353","journal-title":"IEEE\/RSJ Int Conf Intell Robots Syst"},{"issue":"11","key":"413_CR12","doi-asserted-by":"publisher","first-page":"887","DOI":"10.1016\/j.robot.2006.05.007","volume":"54","author":"A Brooks","year":"2006","unstructured":"Brooks A, Makarenko A, Williams S, Durrant-Whyte H (2006) Parametric POMDPs for planning in continuous state spaces. Robot Auton Syst 54(11):887\u2013897","journal-title":"Robot Auton Syst"},{"key":"413_CR13","unstructured":"Chia SH, Su KL, Guo JH, Chung CY (2010) Ant colony system based mobile robot path planning. In: 4th International conference on genetic and evolutionary computing, Shenzhen, China"},{"key":"413_CR14","volume-title":"Elements of information-theory","author":"T Cover","year":"2006","unstructured":"Cover T, Thomas J (2006) Elements of information-theory, 2nd edn. Wiley, Hoboken","edition":"2"},{"key":"413_CR15","doi-asserted-by":"crossref","unstructured":"Dai R, Cochran JE (2009) Path planning for multiple unmanned aerial vehicles by parameterized cornu-spirals. In: Conference paper in proceedings of the American control conference, pp 2391\u20132396","DOI":"10.1109\/ACC.2009.5159914"},{"key":"413_CR16","doi-asserted-by":"crossref","unstructured":"Freundlich C, Mordohai P, Zavlanos MM (2015) Optimal path planning and resource allocation for active target localization. In: American control conference, Chicago, IL, USA, 2015, pp 3088\u20133093","DOI":"10.1109\/ACC.2015.7171807"},{"issue":"12","key":"413_CR17","doi-asserted-by":"publisher","first-page":"1258","DOI":"10.1016\/j.robot.2013.09.004","volume":"61","author":"Enric Galceran","year":"2013","unstructured":"Galceran Enric, Carreras Marc (2013) A survey on coverage path planning for robotics. Robot Auton Syst 61(12):1258\u20131276","journal-title":"Robot Auton Syst"},{"key":"413_CR18","doi-asserted-by":"crossref","unstructured":"Hrabar S (2008) 3D path planning and stereo-based obstacle avoidance for rotorcraft UAVs. In: IEEE\/RSJ international conference on intelligent robots and systems, nice, France, 22\u201326 Sept 2008, pp 807\u2013814","DOI":"10.1109\/IROS.2008.4650775"},{"key":"413_CR19","doi-asserted-by":"crossref","unstructured":"Lanillos P, Besada-Portas E, Pajares G, Ruz JJ (2012) Minimum time search for lost targets using cross entropy optimization. IEEE\/RSJ International Conference on Intelligent Robots and Systems, pp 602\u2013609","DOI":"10.1109\/IROS.2012.6385510"},{"key":"413_CR20","doi-asserted-by":"crossref","unstructured":"Lanillos P, Zuluaga JY, Ruz J, Besada-Portas E (2013) A Bayesian approach for constrained multi-agent minimum time search in uncertain dynamic domains. In: Proceedings of the 15th annual conference on genetic and evolutionary computation. ACM, pp 391\u2013398","DOI":"10.1145\/2463372.2463417"},{"key":"413_CR21","doi-asserted-by":"crossref","unstructured":"Lanillos P, Gan SK, Besada-Portas E, Pajares G, Sukkarieh S (2014) Multi-UAV target search using decentralized gradient-based negotiation with expected observation. In: Information sciences, 282, 2014, pp 92\u2013110","DOI":"10.1016\/j.ins.2014.05.054"},{"key":"413_CR22","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1057\/palgrave.jors.2601352","volume":"53","author":"A Larsen","year":"2002","unstructured":"Larsen A, Madsen O, Solomon M (2002) Partially dynamic vehicle routing-models and algorithms. J Oper Res Soc 53:637\u2013646","journal-title":"J Oper Res Soc"},{"key":"413_CR23","unstructured":"Lau H (2007) Optimal search in structured environments, PhD thesis, University of Technology, Sydney"},{"key":"413_CR24","doi-asserted-by":"crossref","unstructured":"Lau H, Dissanayake G (2005) Optimal search for multiple targets in a built environment. In: Proceedings of the IEEE\/RSJ international conference intelligent robots and systems","DOI":"10.1109\/IROS.2005.1544986"},{"key":"413_CR25","doi-asserted-by":"crossref","unstructured":"Lin Y, Saripalli S (2014) Path planning using 3D dubins curve for unmanned aerial vehicles. In: Proceedings of the IEEE international conference on unmanned aircraft systems (ICUAS), Orlando, FL, USA, 27\u201330 May 2014, pp 296\u2013304","DOI":"10.1109\/ICUAS.2014.6842268"},{"key":"413_CR26","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1016\/S0377-2217(98)00315-4","volume":"118","author":"FH Liu","year":"1999","unstructured":"Liu FH, Shen SY (1999) A route-neighborhood-based metaheuristic for vehicle routing problem with time windows. Eur J Oper Res 118:485\u2013504","journal-title":"Eur J Oper Res"},{"key":"413_CR27","doi-asserted-by":"crossref","unstructured":"Lo N, Berger J, Noel M (2012) Toward optimizing static target search path planning. In: IEEE symposium on computational intelligence for security and defence applications, Ottawa, Canada, pp 1\u20137","DOI":"10.1109\/CISDA.2012.6291538"},{"issue":"12","key":"413_CR28","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.robot.2016.08.001","volume":"86","author":"TT Mac","year":"2016","unstructured":"Mac TT, Copot C, Tran DT, De Keyser R (2016) Heuristic approaches in robot path planning: a survey. Robot Auton Syst 86(12):13\u201328","journal-title":"Robot Auton Syst"},{"key":"413_CR29","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1007\/BF02023004","volume":"41","author":"IH Osman","year":"1993","unstructured":"Osman IH (1993) Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Ann Oper Res 41:421\u2013451","journal-title":"Ann Oper Res"},{"key":"413_CR30","unstructured":"Otte MW (2017) A survey of machine learning approaches to robotic path-planning. University of Colorado at Boulder, Report, August 2017, p 93. \n                    https:\/\/www.cs.colorado.edu\/~mozer\/Teaching\/Computational%20Modeling%20Prelim\/Otte.pdf"},{"key":"413_CR31","doi-asserted-by":"publisher","first-page":"1","DOI":"10.5772\/7789","volume":"9","author":"Xingguang Peng","year":"2012","unstructured":"Peng Xingguang, Demin Xu (2012) Intelligent online path planning for UAVs in adversarial environments. Int J Adv Robot Syst 9:1\u201312","journal-title":"Int J Adv Robot Syst"},{"key":"413_CR32","doi-asserted-by":"crossref","unstructured":"Perez-Carabaza S, Besada-Portas E, Lopez-Orozco JA, de la Cruz JM (2016) A real world multi-uav evolutionary planner for minimum time target detection. In: Proceedings of the genetic and evolutionary computation conference. ACM, pp 981\u2013988","DOI":"10.1145\/2908812.2908876"},{"key":"413_CR33","first-page":"395","volume":"17","author":"PO Pettersson","year":"2006","unstructured":"Pettersson PO, Doherty P (2006) Probabilistic roadmap based path planning for an autonomous unmanned helicopter. J Intell Fuzzy Syst 17:395\u2013405","journal-title":"J Intell Fuzzy Syst"},{"key":"413_CR34","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/s10472-009-9120-2","volume":"52","author":"I Rekleitis","year":"2008","unstructured":"Rekleitis I, New AP, Rankin ES, Choset H (2008) Efficient boustrophedon multi-robot coverage: an algorithmic approach. Ann Math Artif Intell 52:109\u2013142","journal-title":"Ann Math Artif Intell"},{"key":"413_CR35","unstructured":"Rylander B, Foster J (2001) Computational complexity and genetic algorithms. In: Proceedings of the world science and engineering society\u2019s conference on soft computing, advances in fuzzy systems and evolutionary computation. World Science and Engineering Society Press, pp 248\u2013253"},{"key":"413_CR36","doi-asserted-by":"crossref","unstructured":"Rylander B, Soule T, Foster J (2001) Computational complexity, genetic programming, and implications. In: Proceedings of the European genetic programming conference","DOI":"10.1007\/3-540-45355-5_28"},{"issue":"2","key":"413_CR37","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1007\/s10458-007-9026-5","volume":"17","author":"S Seuken","year":"2008","unstructured":"Seuken S, Zilberstein S (2008) Formal models and algorithms for decentralized decision making under uncertainty. Auton Agent Multi-Agent Syst 17(2):190\u2013250","journal-title":"Auton Agent Multi-Agent Syst"},{"key":"413_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1007\/3-540-49481-2_30","volume-title":"Principles and practice of constraint programming","author":"P Shaw","year":"1998","unstructured":"Shaw P (1998) Using constraint programming and local search methods to solve vehicle routing problems. In: Maher M, Puget J-F (eds) Principles and practice of constraint programming. Lecture Notes in Computer Science. Springer, New York, pp 417\u2013431"},{"key":"413_CR39","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1287\/opre.35.2.254","volume":"35","author":"MM Solomon","year":"1987","unstructured":"Solomon MM (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper Res 35:254\u2013265","journal-title":"Oper Res"},{"key":"413_CR40","volume-title":"Theory of optimal search","author":"LD Stone","year":"1975","unstructured":"Stone LD (1975) Theory of optimal search. Academic Press, New York"},{"issue":"8","key":"413_CR41","doi-asserted-by":"publisher","first-page":"2076","DOI":"10.2514\/1.G002314","volume":"40","author":"Chuangchuang Sun","year":"2017","unstructured":"Sun Chuangchuang, Liu Yen-Chen, Dai Ran, Grymin David (2017) Two approaches for path planning of unmanned aerial vehicles with avoidance zones. J Guid Control Dyn 40(8):2076\u20132083","journal-title":"J Guid Control Dyn"},{"issue":"3","key":"413_CR42","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1023\/B:AURO.0000025793.46961.f6","volume":"16","author":"J Svennebring","year":"2004","unstructured":"Svennebring J, Koenig S (2004) Building terrain-covering ant robots: a feasibility study. Auton Robots 16(3):313\u2013332","journal-title":"Auton Robots"},{"issue":"2","key":"413_CR43","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1109\/MRA.2009.932529","volume":"16","author":"J Tisdale","year":"2009","unstructured":"Tisdale J, Zuwhan K, Hedrick JK (2009) Autonomous UAV path planning and Estimation: an online path planning framework for cooperative search and localization. IEEE Robot Autom Mag 16(2):35\u201342","journal-title":"IEEE Robot Autom Mag"},{"issue":"5","key":"413_CR44","doi-asserted-by":"publisher","first-page":"662","DOI":"10.1109\/TRA.2002.804040","volume":"18","author":"R Vidal","year":"2002","unstructured":"Vidal R, Shakernia O, Kim HJ, Shim DH, Sastry S (2002) Probabilistic pursuit-evasion games: theory, implementation, and experimental evaluation. IEEE Trans Robot Autom 18(5):662\u2013669","journal-title":"IEEE Trans Robot Autom"},{"key":"413_CR45","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1002\/(SICI)1520-6750(199804)45:3<243::AID-NAV1>3.0.CO;2-7","volume":"45","author":"AR Washburn","year":"1998","unstructured":"Washburn AR (1998) Branch and bound methods for a search problem. Nav Res Logist 45:243\u2013257","journal-title":"Nav Res Logist"},{"key":"413_CR46","doi-asserted-by":"crossref","unstructured":"Wong S, MacDonald B (2003) A topological coverage algorithm for mobile robots. In: Proceedings of the IEEE\/RSJ international conference on intelligent robots and systems, Las Vegas, 2003, pp 1685\u20131690","DOI":"10.1109\/IROS.2003.1248886"},{"key":"413_CR47","doi-asserted-by":"crossref","unstructured":"Wood J, Hedrick K (2011) Multi-agent path planning for an unknown number of targets over dynamic space partitions. In: 50th IEEE conference on decision and control and european control conference, Orlando, FL, USA, 2011, pp 564\u2013569","DOI":"10.1109\/CDC.2011.6160717"},{"issue":"1","key":"413_CR48","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1109\/TSMCB.2003.811769","volume":"34","author":"S Yang","year":"2004","unstructured":"Yang S, Luo C (2004) A neural network approach to complete coverage path planning. IEEE Trans Syst Man Cybern B Cybern 34(1):718\u2013724","journal-title":"IEEE Trans Syst Man Cybern B Cybern"},{"key":"413_CR49","unstructured":"Yang Y, Minai A, Polycarpou M (2005) Evidential map building approaches for multi-UAV cooperative search. In: Proceedings of the American control conference"},{"issue":"2","key":"413_CR50","doi-asserted-by":"publisher","first-page":"541","DOI":"10.1109\/TMECH.2014.2301459","volume":"20","author":"H Yu","year":"2015","unstructured":"Yu H, Meier K, Argyle M, Beard RW (2015) Cooperative path planning for target tracking in Urban environments using unmanned air and ground vehicles. IEEE\/ASME Trans Mechatron 20(2):541\u2013552","journal-title":"IEEE\/ASME Trans Mechatron"},{"key":"413_CR51","doi-asserted-by":"crossref","unstructured":"Yuan S, Lau H, Liu DK, Huang SD, Dissanayake G, Pagac D, Pratley T (2009) Simultaneous dynamic scheduling and collision-free path planning for multiple autonomous vehicles. In: International conference on information and automation, Macau, China, 2009","DOI":"10.1109\/ICINFA.2009.5204979"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-019-00413-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-019-00413-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-019-00413-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,14]],"date-time":"2020-05-14T23:28:50Z","timestamp":1589498930000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-019-00413-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,16]]},"references-count":51,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,10]]}},"alternative-id":["413"],"URL":"https:\/\/doi.org\/10.1007\/s10878-019-00413-1","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,16]]},"assertion":[{"value":"16 May 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}