Academic
Publications
Speeding up moving-target search

Speeding up moving-target search,10.1145/1329125.1329353,Sven Koenig,Maxim Likhachev,Xiaoxun Sun

Speeding up moving-target search   (Citations: 16)
BibTex | RIS | RefWorks Download
In this paper, we study moving-target search, where an agent (= hunter) has to catch a moving target (= prey). The agent does not necessarily know the terrain initially but can observe it within a certain sensor range around itself. It uses the strategy to always move on a shortest presumed unblocked path toward the target, which is a reasonable strategy for computer-controlled characters in video games. We study how the agent can find such paths faster by exploiting the fact that it performs A* searches repeat- edly. To this end, we extend Adaptive A*, an incremental heuristic search method, to moving-target search and demonstrate experi- mentally that the resulting MT-Adaptive A* is faster than isolated A* searches and, in many situations, also D* Lite, a state-of-the-art incremental heuristic search method. In particular, it is faster than D* Lite by about one order of magnitude for moving-target search in known and initially unknown mazes if both search methods use the same informed heuristics.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...In a recent paper, Koenig et al. [11] introduce a variant of A* for the moving target search problem that incorporates adaptation, thereby showing significant computational advantages...
    • ...In this case, a world is assumed with a simple grid layout (much in line with [11]), see Figure 2...
    • ...For instance, a comparison with MT-adaptive A* (cf. [11]) would be very interesting...

    Ard C. M. Alet al. Moving Target Search Using Theory of Mind

    • ...Experiments demonstrated that TAO-MTP well outperforms extended moving-target search (eMTS, [13]), path refinement movingtarget search (PR MTS, [1], [14]), moving-target adaptive A* (MTAA*, [15]), and generalized adaptive A* (GAA*, [16])...
    • ...1) Employing a heuristic function to learn shortest path distances between pairs of states on a map: including moving-target search (MTS) family of algorithms [13], [17]‐[20] and the state-of-the-art MTAA* [15], GAA* [16], and fringe-retrieving A* (FRA*) [21] algorithms...
    • ...3) MTAA*: used a version of lazy MTAA* (forward search) that searches forward from the current cell of the hunter to the current cell of the prey [15]...

    Mingliang Xuet al. Moving-Target Pursuit Algorithm Using Improved Tracking Strategy

    • ...The target search in agent systems has been researched in many variations: with moving targets [2, 3, 4], and in single-agent systems [5]...

    Patrick Edigeret al. Routing in the triangular grid with evolved agents

    • ...D* [15,16 ], Focused D* [17], D* Lite [18–20 ]a nd MT-Adaptive A* [21] are some of the well-known optimal incremental heuristic search algorithms applied to path planning domain...

    Cagatay Undegeret al. Multi-agent real-time pursuit

    • ...There are only a variety of approaches of learning and any-time algorithms that yield good solutions but none are guaranteed to return optimal solutions [6, 2, 7, 4]...

    Carsten Moldenhaueret al. Optimal Solutions for Moving Target Search (Extended Abstract)

Sort by: