The Trailblazer Search: A New Method for Searching and Capturing Moving Targets

Fumihiko Chimura, Mario TokoroAAAI 1994

Abstract

Real-time heuristic search for moving targets often suffers from inefficiencies in obstacle-rich environments due to a lack of memory. We present Trailblazer Search (TBS), an algorithm that maintains a "Trail" of previously visited nodes to build a routing table. By switching to a "Chase Phase" once a target intersects this trail, TBS significantly reduces the physical steps required for capture. Experimental results demonstrate up to a 100-fold efficiency gain over traditional Moving Target Search (MTS) in complex grids.

Introduction

In real-time heuristic search, the Moving Target Search (MTS) problem requires a solver to capture a target that is also moving. Traditional approaches, such as those established by Ishida and Korf (1991), allow for constant-time decision-making by updating local distance estimates. However, these methods often struggle in environments with high obstacle density. Without a memory of the environment's layout, solvers frequently oscillate or revisit nodes, as simple heuristics like Manhattan distance fail to account for dead ends and walls.

The Trailblazer Search (TBS) Algorithm

Trailblazer Search (TBS) addresses these inefficiencies by recording every step taken in a graph structure called the Trail. This trail is used to compute a routing table via Dijkstra’s shortest path algorithm, representing the solver's "known world."

The algorithm operates in two phases:

  1. Search Phase: When the target is in an unmapped area, the solver uses a hill-climbing heuristic to move toward the target's last known position.
  2. Chase Phase: As soon as the target steps onto a node within the solver's Trail, the solver switches to the Chase Phase. It then utilizes the pre-calculated Map to follow the optimal path to intercept the target.

While TBS incurs higher computational overhead to maintain the map, the authors argue that the time saved in physical movement—which is orders of magnitude slower than CPU cycles—results in a net gain in real-world efficiency.

Experimental Evaluation

The performance of TBS was evaluated against MTS in a 50x50 toroidal grid with obstacle ratios ranging from 0% to 40%. Four target strategies were tested: Avoid (fleeing), Stationary, Random, and Meet (seeking the solver).

Comparison of search steps for TBS (a) and MTS (b) across varying obstacle ratios and target strategies.

Results and Discussion

As shown in the comparative plots in Figure 1, the performance gap between TBS and MTS widens significantly as the environment becomes more complex. At a 40% obstacle ratio, TBS captured the "Meet" target in approximately 1/100th the number of steps required by MTS.

A notable finding is the "Meet" paradox: while a target trying to meet the solver can confuse traditional MTS by constantly altering the state space, it actually aids TBS. A target seeking the solver is more likely to intersect the solver's Trail early, triggering the Chase Phase and leading to rapid capture. Conversely, in open spaces (0% obstacles), TBS can be slightly less efficient than MTS because it strictly follows its known map rather than exploring potentially shorter, unmapped diagonal paths.

Conclusion

TBS demonstrates that incorporating memory into real-time search drastically improves efficiency in obstacle-filled environments. By leveraging the "Trail" to transition from heuristic search to optimal chasing, TBS overcomes the limitations of memoryless algorithms. Future work will focus on scaling TBS for larger environments and adapting it to dynamic maps where obstacles may change position.

Summary updated

BibTeX
@inproceedings{chimura1994trailblazer,
  author = {Fumihiko Chimura and Mario Tokoro},
  title = {{The Trailblazer Search: A New Method for Searching and Capturing Moving Targets}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure