Xiaoxun Sun

ICAPS Conference 2012 Conference Paper

Incremental ARA*: An Incremental Anytime Search Algorithm for Moving-Target Search

• Xiaoxun Sun
• Tansel Uras
• Sven Koenig
• William Yeoh 0001

Moving-target search, where a hunter has to catch a moving target, is an important problem for video game developers. In our case, the hunter repeatedly moves towards the target and thus has to solve similar search problems repeatedly. We develop Incremental ARA* (I-ARA*) for this purpose, the first incremental anytime search algorithm for moving-target search in known terrain. We provide an error bound on the lengths of the paths found by I-ARA* and show experimentally in known four-neighbor gridworlds that I-ARA* can be used with smaller time limits between moves of the hunter than competing state-of-the-art moving-target search algorithms, namely repeated A*, G-FRA*, FRA*, and sometimes repeated ARA*. The hunter tends to make more moves with I-ARA* than repeated A*, G-FRA* or FRA*, which find shortest paths for the hunter, but fewer moves with I-ARA* than repeated ARA*, which finds suboptimal paths for the hunter like I-ARA*. Also, the error bounds on the lengths of the paths of the hunter tend to be smaller with I-ARA* than repeated ARA*.

AAMAS Conference 2011 Conference Paper

Incremental DCOP Search Algorithms for Solving Dynamic DCOPs

• William Yeoh
• Pradeep Varakantham
• Xiaoxun Sun
• Sven Koenig

Distributed constraint optimization problems (DCOPs) are well-suited for modeling multi-agent coordination problems. However, most research has focused on developing algorithms for solving static DCOPs. In this paper, we model dynamic DCOPs as sequences of (static) DCOPs with changes from one DCOP to the next one in the sequence. We introduce the ReuseBounds procedure, which can be used by any-space ADOPT and any-space BnB-ADOPT to find cost-minimal solutions for all DCOPs in the sequence faster than by solving each DCOP individually. This procedure allows those agents that are guaranteed to remain unaffected by a change to reuse their lower and upper bounds from the previous DCOP when solving the next one in the sequence. Our experimental results show that the speedup gained from this procedure increases with the amount of memory the agents have available.

AAMAS Conference 2011 Conference Paper

Tree Adaptive A*

• Carlos Hern
• aacute; ndez
• Xiaoxun Sun
• Sven Koenig
• Pedro Meseguer

Incremental heuristic search algorithms can solve sequences of similar search problems potentially faster than heuristic search algorithms that solve each search problem from scratch. So far, there existed incremental heuristic search algorithms (such as Adaptive A*) that make the h-values of the current A* search more informed, which can speed up future A* searches, and incremental heuristic search algorithms (such as D* Lite) that change the search tree of the current A* search to the search tree of the next A* search, which can be faster than constructing it from scratch. In this paper, we present Tree Adaptive A*, which applies to goal-directed navigation in unknown terrain and builds on Adaptive A* but combines both classes of incremental heuristic search algorithms in a novel way. We demonstrate experimentally that it can run faster than Adaptive A*, Path Adaptive A* and D* Lite, the top incremental heuristic search algorithms in the context of goal-directed navigation in unknown grids.

AAMAS Conference 2010 Conference Paper

Generalized Fringe-Retrieving A*: Faster Moving Target Search on State Lattices

• Xiaoxun Sun
• William Yeoh
• Sven Koenig

Moving target search is important for robotics applicationswhere unmanned ground vehicles (UGVs) have to followother friendly or hostile UGVs. Artificial intelligence researchers have recently used incremental search to speedup the computation of a simple strategy for the hunter. The fastest incremental search algorithm, Fringe-RetrievingA*, solves moving target search problems only on two-dimensional grids, which are rather unrealistic models forrobotics applications. We therefore generalize it to Generalized Fringe-Retrieving A*, which solves moving target searchproblems on arbitrary graphs, including the state latticesused for UGV navigation.

AAMAS Conference 2010 Conference Paper

Moving Target D* Lite

• Xiaoxun Sun
• William Yeoh
• Sven Koenig

Incremental search algorithms, such as Generalized Fringe-Retrieving A* and D* Lite, reuse search trees from previous searches to speed up the current search and thus oftenfind cost-minimal paths for series of similar search problemsfaster than by solving each search problem from scratch. However, existing incremental search algorithms have limitations. For example, D* Lite is slow on moving targetsearch problems, where both the start and goal states canchange over time. In this paper, we therefore introduceMoving Target D* Lite, an extension of D* Lite that usesthe principle behind Generalized Fringe-Retrieving A* to repeatedly calculate a cost-minimal path from the hunter tothe target in environments whose blockages can change overtime. We demonstrate experimentally that Moving TargetD* Lite is four to five times faster than Generalized AdaptiveA*, which so far was believed to be the fastest incrementalsearch algorithm for solving moving target search problemsin dynamic environments.

SoCS Conference 2010 Conference Paper

Real-Time Search in Dynamic Worlds

• David Bond
• Niels A. Widger
• Wheeler Ruml
• Xiaoxun Sun

For problems such as pathfinding in video games and robotics, a search algorithm must be real-time (return the next move within a fixed time bound) and dynamic (accommodate edge costs that can increase and decrease before the goal is reached). Existing real-time search algorithms, such as LSS-LRTA*, can handle edge cost increases but do not handle edge cost decreases. Existing dynamic search algorithms, such as D* Lite, are not real-time. We show how these two families of algorithms can be combined using bidirectional search, producing Real-Time D* (RTD*), the first real-time search algorithm designed for dynamic worlds. Our empirical evaluation shows that, for dynamic grid pathfinding, RTD* results in significantly shorter trajectories than either LSS-LRTA* or naive real-time adaptations of D* Lite because of its ability to opportunistically exploit shortcuts.

IJCAI Conference 2009 Conference Paper

• William Yeoh
• Xiaoxun Sun
• Sven Koenig

Distributed Constraint Optimization (DCOP) is a key technique for solving agent coordination problems. Because finding cost-minimal DCOP solutions is NP-hard, it is important to develop mechanisms for DCOP search algorithms that trade off their solution costs for smaller runtimes. However, existing tradeoff mechanisms do not provide relative error bounds. In this paper, we introduce three tradeoff mechanisms that provide such bounds, namely the Relative Error Mechanism, the Uniformly Weighted Heuristics Mechanism and the Non-Uniformly Weighted Heuristics Mechanism, for two DCOP algorithms, namely ADOPT and BnB-ADOPT. Our experimental results show that the Relative Error Mechanism generally dominates the other two tradeoff mechanisms for ADOPT and the Uniformly Weighted Heuristics Mechanism generally dominates the other two tradeoff mechanisms for BnB-ADOPT.

IJCAI Conference 2009 Conference Paper

• Xiaoxun Sun
• William Yeoh
• Sven Koenig

Incremental search algorithms reuse information from previous searches to speed up the current search and are thus often able to find shortest paths for series of similar search problems faster than by solving each search problem independently from scratch. However, they do poorly on moving target search problems, where both the start and goal cells change over time. In this paper, we thus develop Fringe-Retrieving A* (FRA*), an incremental version of A* that repeatedly finds shortest paths for moving target search in known gridworlds. We demonstrate experimentally that it runs up to one order of magnitude faster than a variety of state-of-the-art incremental search algorithms applied to moving target search in known gridworlds.

AAMAS Conference 2009 Conference Paper

Dynamic Fringe-Saving A*

• Xiaoxun Sun
• William Yeoh
• Sven Koenig

Fringe-Saving A* is an incremental version of A* that repeatedly finds shortest paths from a fixed start cell to a fixed goal cell in a known gridworld in case the traversability of cells changes over time. It restores the content of the OPEN and CLOSED lists of A* at the point in time when an A* search for the current search problem could deviate from the A* search for the previous search problem. Thus, Fringe- Saving A* reuses the beginning of the previous A* search that is identical to the current A* search. In this paper, we generalize the correctness proof of Fringe-Saving A* to cover the case where the goal cell changes over time in addition to the traversability of cells. We then apply Fringe-Saving A* to the problem of moving an agent along a shortest path from its current cell to a fixed destination cell in a known gridworld, where the shortest path is replanned whenever the traversability of cells changes. Our experimental results show that the resulting Dynamic Fringe-Saving A* algorithm can outperform both repeated A* searches and D* Lite (a state-of-the-art incremental version of A*) in highly dynamic gridworlds, with runtime savings of up to a factor of about 2. 5.

ICAPS Conference 2009 Conference Paper

Path-Adaptive A* for Incremental Heuristic Search in Unknown Terrain

• Carlos Hernández Ulloa
• Pedro Meseguer
• Xiaoxun Sun
• Sven Koenig

Adaptive A* is an incremental version of A* that updates the h-values of the previous A* search to make them more informed and thus future A* searches more focused. In this paper, we show how the A* searches performed by Adaptive A* can reuse part of the path of the previous search and terminate before they expand a goal state, resulting in Path-Adaptive A*. We demonstrate experimentally that Path-Adaptive A* expands fewer states per search and runs faster than Adaptive A* when solving path-planning problems in initially unknown terrain.

AAMAS Conference 2009 Conference Paper

Simple Optimization Techniques for A*-Based Search

• Xiaoxun Sun
• William Yeoh
• Po-An Chen
• Sven Koenig

In this paper, we present two simple optimizations that can reduce the number of priority queue operations for A* and its extensions. Basically, when the optimized search algorithms expand a state, they check whether they will expand a successor of the state next. If so, they do not first insert it into the priority queue and then immediately remove it again. These changes might appear to be trivial but are well suited for Generalized Adaptive A*, an extension of A*. Our experimental results indeed show that they speed up Generalized Adaptive A* by up to 30 percent if its priority queue is implemented as a binary heap.

JAAMAS Journal 2008 Journal Article

Comparing real-time and incremental heuristic search for real-time situated agents

• Sven Koenig
• Xiaoxun Sun

Abstract Real-time situated agents, such as characters in real-time computer games, often do not know the terrain in advance but automatically observe it within a certain range around themselves. They have to interleave searches with action executions to make the searches tractable when moving autonomously to user-specified coordinates. The searches face real-time requirements since it is important that the agents be responsive to the commands of the users and move smoothly. In this article, we compare two classes of fast heuristic search methods for these navigation tasks that speed up A* searches in different ways, namely real-time heuristic search and incremental heuristic search, to understand their advantages and disadvantages and make recommendations about when each one should be used. We first develop a competitive real-time heuristic search method. LSS-LRTA* is a version of Learning Real-Time A* that uses A* to determine its local search spaces and learns quickly. We analyze the properties of LSS-LRTA* and then compare it experimentally against the state-of-the-art incremental heuristic search method D* Lite on our navigation tasks, for which D* Lite was specifically developed, resulting in the first comparison of real-time and incremental heuristic search in the literature. We characterize when to choose each one of the two heuristic search methods, depending on the search objective and the kind of terrain. Our experimental results show that LSS-LRTA* can outperform D* Lite under the right conditions, namely when there is time pressure or the user-supplied h-values are generally not misleading.

AAMAS Conference 2008 Conference Paper

Generalized Adaptive A*

• Xiaoxun Sun
• Sven Koenig
• William Yeoh

Agents often have to solve series of similar search problems. Adaptive A* is a recent incremental heuristic search algorithm that solves series of similar search problems faster than A* because it updates the h-values using information from previous searches. It basically transforms consistent hvalues into more informed consistent h-values. This allows it to find shortest paths in state spaces where the action costs can increase over time since consistent h-values remain consistent after action cost increases. However, it is not guaranteed to find shortest paths in state spaces where the action costs can decrease over time because consistent h-values do not necessarily remain consistent after action cost decreases. Thus, the h-values need to get corrected after action cost decreases. In this paper, we show how to do that, resulting in Generalized Adaptive A* (GAA*) that finds shortest paths in state spaces where the action costs can increase or decrease over time. Our experiments demonstrate that Generalized Adaptive A* outperforms breadth-first search, A* and D* Lite for moving-target search, where D* Lite is an alternative state-of-the-art incremental heuristic search algorithm that finds shortest paths in state spaces where the action costs can increase or decrease over time.

AAMAS Conference 2008 Conference Paper

Trading Off Solution Quality for Faster Computation in DCOP Search Algorithms

• William Yeoh
• Sven Koenig
• Xiaoxun Sun

Distributed Constraint Optimization (DCOP) is a key technique for solving multiagent coordination problems. Unfortunately, finding minimal-cost DCOP solutions is NP-hard. We therefore propose two mechanisms that trade off the solution costs of two DCOP search algorithms (ADOPT and BnB-ADOPT) for smaller runtimes, namely the Inadmissible Heuristics Mechanism and the Relative Error Mechanism. The solution costs that result from these mechanisms are bounded by a more meaningful quantity than the solution costs that result from the existing Absolute Error Mechanism since they both result in solution costs that are larger than minimal by at most a user-specified percentage. Furthermore, the Inadmissible Heuristics Mechanism experimentally dominates both the Absolute Error Mechanism and the Relative Error Mechanism for BnB-ADOPT and is generally no worse than them for ADOPT.

IJCAI Conference 2007 Conference Paper

• Xiaoxun Sun
• Sven Koenig

In this paper, we develop Fringe-Saving A* (FSA*), an incremental version of A* that repeatedly finds shortest paths in a known gridworld from a given start cell to a given goal cell while the traversability costs of cells increase or decrease. The first search of FSA* is the same as that of A*. However, FSA* is able to find shortest paths during the subsequent searches faster than A* because it reuses the beginning of the immediately preceeding A* search tree that is identical to the current A* search tree. FSA* does this by restoring the content of the OPEN list of A* at the point in time when an A* search for the current search problem could deviate from the A* search for the immediately preceeding search problem. We present first experimental results that demonstrate that FSA* can have a runtime advantage over A* and Lifelong Planning A* (LPA*), an alternative incremental version of A*.

IJCAI Conference 2007 Conference Paper

• Xiaoxun Sun
• Marek J. Druzdzel
• Changhe Yuan

In this paper we propose the Dynamic Weighting A* (DWA*) search algorithm for solving MAP problems in Bayesian networks. By exploiting asymmetries in the distribution of MAP variables, the algorithm is able to greatly reduce the search space and offer excellent performance both in terms of accuracy and efficiency.

AAMAS Conference 2007 Conference Paper

Speeding up Moving-Target Search

• Sven Koenig
• Maxim Likhachev
• Xiaoxun Sun

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 repeatedly. To this end, we extend Adaptive A *, an incremental heuristic search method, to moving-target search and demonstrate experimentally 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.

SODA Conference 2006 Conference Paper

Finding nucleolus of flow game

• Xiaotie Deng
• Qizhi Fang
• Xiaoxun Sun