aacute; ndez

AAMAS Conference 2012 Conference Paper

Time Bounded Adaptive A*

• Carlos Hern
• aacute; ndez
• Jorge Baier
• Tansel Uras
• Sven Koenig

n this paper, we investigate real-time path planning in static terrain, as needed in video games. We introduce the game time model, where time is partitioned into uniform time intervals, an agent can execute one movement during each time interval, and search and movements are done in parallel. The objective is to move the agent from its start location to its goal location in as few time intervals as possible. For known terrain, we show experimentally that Time-Bounded A* (TBA*), an existing real-time search algorithm for undirected terrain, needs fewer time intervals than two state-of-the-art real-time search algorithms and about the same number of time intervals as A*. TBA*, however, cannot be used when the terrain is not known initially. For initially partially or completely unknown terrain, we thus propose a new search algorithm. Our Time-Bounded Adaptive A* (TBAA*) extends TBA* to on-line path planning with the freespace assumption by combining it with Adaptive A*. We prove that TBAA* either moves the agent from its start location to its goal location or detects that this is impossible - an important property since many existing realtime search algorithms are not able to detect efficiently that no path exists. Furthermore, TBAA* can eventually move the agent on a cost-minimal path from its start location to its goal location if it resets the agent into its start location whenever it reaches its goal location. We then show experimentally in initially partially or completely unknown terrain that TBAA* needs fewer time intervals than several state-of-the-art complete and real-time search algorithms and about the same number of time intervals as the best compared complete search algorithm, even though it has the advantage over complete search algorithms that the agent starts to move right away.

AAMAS Conference 2011 Conference Paper

Escaping Heuristic Depressions in Real-Time Heuristic Search

• Carlos Hern
• aacute; ndez
• Jorge A. Baier

Heuristic depressions are local minima of heuristic functions. While visiting one them, real-time (RT) search algorithms like LRTA will update the heuristic value for most of their states several times before escaping, resulting in costly solutions. Existing RT search algorithm tackle this problem by doing more search and/or lookahead but do not guide search towards leaving depressions. We present eLSS-LRTA, a new RT search algorithm based on LSSLRTA that actively guides search towards exiting regions with heuristic depressions. We show that our algorithm produces better quality solutions than LSS-LRTA for equal values of lookahead in standard RT benchmarks.

IJCAI Conference 2011 Conference Paper

Real-Time Heuristic Search with Depression Avoidance

• Carlos Hern
• aacute; ndez
• Jorge A. Baier

Heuristics used for solving hard real-time search problems have regions with depressions. Such regions are bounded areas of the search space in which the heuristic function is exceedingly low compared to the actual cost to reach a solution. Real-time search algorithms easily become trapped in those regions since the heuristic values of states in them may need to be updated multiple times, which results in costly solutions. State-of-the-art real-time search algorithms like LSS-LRTA*, LRTA*(k), etc. , improve LRTA*'s mechanism to update the heuristic, resulting in improved performance. Those algorithms, however, do not guide search towards avoiding or escaping depressed regions. This paper presents depression avoidance, a simple real-time search principle to guide search towards avoiding states that have been marked as part of a heuristic depression. We apply the principle to LSS-LRTA* producing aLSS-LRTA*, a new real-time search algorithm whose search is guided towards exiting regions with heuristic depressions. We show our algorithm outperforms LSS-LRTA* in standard real-time benchmarks. In addition we prove aLSS-LRTA* has most of the good theoretical properties of LSS-LRTA*.

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.

IJCAI Conference 2007 Conference Paper

• Alan M. Frisch
• Matthew Grum
• Chris Jefferson
• Bernadette Mart
• iacute; nez Hern
• aacute; ndez
• Ian Miguel

ESSENCE is a new formal language for specifying combinatorial problems in a manner similar to natural rigorous specifications that use a mixture of natural language and discrete mathematics. ESSENCE provides a high level of abstraction, much of which is the consequence of the provision of decision variables whose values can be combinatorial objects, such as tuples, sets, multisets, relations, partitions and functions. ESSENCE also allows these combinatorial objects to be nested to arbitrary depth, thus providing, for example, sets of partitions, sets of sets of partitions, and so forth. Therefore, a problem that requires finding a complex combinatorial object can be directly specified by using a decision variable whose type is precisely that combinatorial object.

IJCAI Conference 2007 Conference Paper

• Susana Fern
• aacute; ndez
• Ricardo Aler
• Daniel Borrajo

As any other problem solving task that employs search, AI Planning needs heuristics to efficiently guide the problem-space exploration. Machine learning (ML) provides several techniques for automatically acquiring those heuristics. Usually, a planner solves a problem, and a ML technique generates knowledge from the search episode in terms of complete plans (macro-operators or cases), or heuristics (also named control knowledge in planning). In this paper, we present a novel way of generating planning heuristics: we learn heuristics in one planner and transfer them to another planner. This approach is based on the fact that different planners employ different search bias. We want to extract knowledge from the search performed by one planner and use the learned knowledge on another planner that uses a different search bias. The goal is to improve the efficiency of the second planner by capturing regularities of the domain that it would not capture by itself due to its bias. We employ a deductive learning method (\ebl) that is able to automatically acquire control knowledge by generating bounded explanations of the problem-solving episodes in a Graphplan-based planner. Then, we transform the learned knowledge so that it can be used by a bidirectional planner.

IJCAI Conference 2007 Conference Paper

• Santiago Fern
• aacute; ndez
• Alex Graves
• J
• uuml; rgen Schmidhuber

Modelling data in structured domains requires establishing the relations among patterns at multiple scales. When these patterns arise from sequential data, the multiscale structure also contains a dynamic component that must be modelled, particularly, as is often the case, if the data is unsegmented. Probabilistic graphical models are the predominant framework for labelling unsegmented sequential data in structured domains. Their use requires a certain degree of a priori knowledge about the relations among patterns and about the patterns themselves. This paper presents a hierarchical system, based on the connectionist temporal classification algorithm, for labelling unsegmented sequential data at multiple scales with recurrent neural networks only. Experiments on the recognition of sequences of spoken digits show that the system outperforms hidden Markov models, while making fewer assumptions about the domain.

IJCAI Conference 2007 Conference Paper

• Carlos Hern
• aacute; ndez
• Pedro Meseguer

We identify some weak points of the LRTA*(k) algorithm in the propagation of heuristic changes. To solve them, we present a new algorithm, LRTA*LS(k), that is based on the selection and up-dating of the interior states of a local space around the current state. It keeps the good theoretical prop-erties of LRTA*(k), while improving substantially its performance. It is related with a lookahead depth greater than 1. We provide experimental evidence of the benefits of the new algorithm on real-time benchmarks with respect to existing approaches.