Multi-Agent Search-Type Problems on Polygons

We present several advancements in search-type problems for fleets of mobile agents operating in two dimensions under the wireless model. Potential hidden target locations are equidistant from a central point, forming either a disk (infinite possible locations) or regular polygons (finite possible locations). Building on the foundational disk evacuation problem, the disk priority evacuation problem with k Servants, and the disk w-weighted search problem, we make improvements on several fronts. First we establish new upper and lower bounds for the n-gon priority evacuation problem with $1$ Servant for n ≤ 13, and for nₖ-gons with $k=2, 3, 4$ Servants, where n₂ ≤ 11, n₃ ≤ 9, and n₄ ≤ 10, offering tight or nearly tight bounds. The only previous results known were a tight upper bound for $k=1$ and $n=6$ and lower bounds for $k=1$ and n ≤ 9. Second, our work improves the best lower bound known for the disk priority evacuation problem with $k=1$ Servant from $4.46798$ to $4.64666$ and for $k=2$ Servants from $3.6307$ to $3.65332$. Third, we improve the best lower bounds known for the disk w-weighted group search problem, significantly reducing the gap between the best upper and lower bounds for w values where the gap was largest. These improvements are based on nearly tight upper and lower bounds for the $11$-gon and $12$-gon w-weighted evacuation problems, while previous analyses were limited only to lower bounds and only to $7$-gons.