2023/09/06 by Miguel A. Lejeune, Lejeune, Miguel, Johannes Ø. Røyset +3
Biochemistry, Genetics and Molecular Biology · Computer Science · #Diffusion and Search Dynamics #FOS: Electrical engineering #FOS: Mathematics #Metaheuristic Optimization Algorithms Research #Optimization and Control (math.OC) #Optimization and Search Problems #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2309.02629
openalex publication_date 2023/09/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In multi-agent search planning for a randomly moving and camouflaging target, we examine heterogeneous searchers that differ in terms of their endurance level, travel speed, and detection ability. This leads to a convex mixed-integer nonlinear program, which we reformulate using three linearization techniques. We develop preprocessing steps, outer approximations via lazy constraints, and bundle-based cutting plane methods to address large-scale instances. Further specializations emerge when the target moves according to a Markov chain. We carry out an extensive numerical study to show the computational efficiency of our methods and to derive insights regarding which approach should be favored for which type of problem instance.