Priority Evacuation in Asymmetric Multi Agent Search

14 concepts10 papers1 proposal

Traditional multi-agent search and evacuation models typically focus on egalitarian goals: minimizing the time it takes for the entire group to reach safety, or minimizing the time for the first agent to discover an exit. However, many real-world and theoretical scenarios feature a stark structural asymmetry where a single high-priority asset—a "queen" or a primary "anchor"—must be evacuated or guided to a target as quickly as possible, while all other agents act as expendable assets to facilitate this single objective.

This paradigm shift introduces unique geometric and algorithmic challenges. By breaking the symmetry of agent roles, systems can achieve significantly faster target acquisition times for the priority asset, but doing so requires balancing a delicate tension between exploration and positioning.

The Geometric Tension: Center vs. Perimeter

To understand why priority search works, consider a foundational geometric problem: a high-priority agent (the queen) and a swarm of helper robots (servants) start at the center of a circular disk. A single exit is hidden somewhere on the disk's perimeter. The servants can move outward to search the perimeter, but the queen must eventually reach the exit to escape.

Where should the queen go while the servants search? As explored by Jurek Czyzowicz et al. in Priority Evacuation from a Disk Using Mobile Robots - (Extended Abstract), the priority agent faces a fundamental geometric dilemma:

  • Staying at the center preserves perfect equidistance to all unsearched areas. If a servant discovers the exit at any random point on the perimeter, the queen's remaining travel distance is exactly the radius of the disk ($R$).
  • Moving early toward the perimeter breaks this symmetry. If the queen moves toward the 12 o'clock position and the exit is discovered there, her final transit time is drastically reduced. However, if the exit is instead discovered at the 6 o'clock position, she must now traverse a much larger distance (up to $2R$), severely worsening the worst-case evacuation time.

This tension between maintaining central positioning to preserve symmetry and moving closer to the boundary to minimize final travel distance is the core optimization challenge in priority-based geometric search.

The Hedging Strategy: Timed Waiting

The key to resolving this dilemma is a coordinated "hedging" strategy. The priority agent should not remain static forever, nor should they blindly rush to the perimeter. Instead, the optimal behavior involves remaining stationary at the geometric center for a precisely calculated duration before moving directionally.

In Priority evacuation from a disk: The case of n ≥ 4, the authors demonstrate that this timed delay allows the priority agent to exploit the initial search coverage of the helper robots. While the queen waits at the center, the servants fan out along symmetric radial paths to divide the angular space evenly—a strategy shown by Sumi Acharjee et al. in Lower Bounds for Shoreline Searching with 2 or More Robots to minimize the maximum possible delay in target detection.

As the servants clear portions of the perimeter without finding the exit, the probability distribution of the exit's location narrows to the remaining unsearched sectors. Once this unsearched angular window is sufficiently small, the queen can begin moving dynamically toward that specific sector. By hedging her trajectory, the queen minimizes her final transit distance to late-discovered targets without risking being caught out of position early on. As a result, the worst-case evacuation time scales inversely with the number of searching agents, strictly outperforming naive centralized waiting strategies.

       Symmetric Search                      Hedging Phase
          (Phase 1)                            (Phase 2)

             (12)                                 (12)
          /   |   \                            /   |   \
         /    |    \                          /    |    \
       (9)---(Q)---(3)                      (9)   (Q)   (3)  <-- Queen moves toward
         \    |    /                          \    |    /        unsearched sector
          \   |   /                            \   |   /
             (6)                                  (6)
      [Servants (s) fan out]               [Servants clear sectors;
       Queen (Q) waits at center]           Queen breaks symmetry]

The Power of Asymmetric Anchors

The intuition behind priority evacuation—designating specific, asymmetric roles to simplify coordination and optimize paths—extends well beyond continuous geometric disks into discrete graphs and state-space searches.

Graph Exploration and Rendezvous

When a team of robots must explore an unknown graph and rendezvous to share maps without wireless communication, symmetric strategies (where all agents move simultaneously) often suffer from high coordination overhead and expanded search spaces. To solve this, Malika Meghjani et al. in Multi-robot exploration and rendezvous on graphs developed distance-aware ranking strategies that designate a single agent as a stationary "anchor" while others actively search. Just like the queen waiting at the center of a disk, fixing an anchor agent drastically simplifies the search space and reduces the total time required for the moving agents to achieve a successful rendezvous.

State-Space Pathfinding

A parallel mechanism operates in heuristic bidirectional search. In Anchor Search: A Unified Framework for Suboptimal Bidirectional Search, Sepehr Lavasani et al. introduce a framework that optimizes search in highly structured or asymmetric state spaces by employing distinct anchor selection policies for the forward and backward search frontiers. Instead of allowing both frontiers to expand symmetrically and meet chaotically in the middle, one direction targets a static goal or a dynamic representative state (an anchor) from the opposing frontier. This asymmetric coordination focuses the search velocity, preventing redundant state expansions and accelerating path discovery.

While prioritizing a single asset yields significant empirical and algorithmic advantages, proving the theoretical limits (lower bounds) of these systems is mathematically challenging.

As Xin Wang notes in Weighted Group Search on the Disk & Improved Lower Bounds for Priority Evacuation, establishing tight theoretical bounds for multi-agent search becomes significantly harder when agent objectives are asymmetric. In a symmetric search, all agents share identical goals and trajectories can be modeled uniformly. In priority search, agents are forced into specialized, heterogeneous roles (e.g., the stationary anchor vs. the expanding searcher).

To narrow the gap between upper and lower performance bounds, researchers must design specialized mathematical relaxation techniques that account for how the priority agent's movement dynamically alters the geometric reachability circles of the entire swarm. Ultimately, these proofs confirm a core truth of search theory: by intentionally breaking symmetry and treating secondary agents as expendable search assets, a collective swarm can guarantee optimal protection and escape times for its highest-value assets.

Key Foundational Work

Multi-robot exploration and rendezvous on graphs (2012) — contributed 2 concept elements to this direction.
Evaluating Strategies for Running from the Cops (2009) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_priority_based_search_coordination_05aed21f,
  title = {priority-based search coordination},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/priority-based-search-coordination/rdr_05aed21f9d0d4b3e81357b5403e845cb},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_priority_based_search_coordination_05aed21f_v1,
  title = {priority-based search coordination},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/priority-based-search-coordination/rdr_05aed21f9d0d4b3e81357b5403e845cb/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake