Author name cluster

Jonathan Schaeffer 0001

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

17 papers

1 author row

ICAPS Conference 2014 Conference Paper

A Comparison of Knowledge-Based GBFS Enhancements and Knowledge-Free Exploration

Richard Valenzano
Nathan R. Sturtevant
Jonathan Schaeffer 0001
Fan Xie 0001

GBFS-based satisficing planners often augment their search with knowledge-based enhancements such as preferred operators and multiple heuristics. These techniques seek to improve planner performance by making the search more informed. In our work, we will focus on how these enhancements impact coverage and we will use a simple technique called epsilon-greedy node selection to demonstrate that planner coverage can also be improved by introducing knowledge-free random exploration into the search. We then revisit the existing knowledge-based enhancements so as to determine if the knowledge these enhancements employ is offering necessary guidance, or if the impact of this knowledge is to add exploration which can be achieved more simply using randomness. This investigation provides further evidence of the importance of preferred operators and shows that the knowledge added when using an additional heuristic is crucial in certain domains, while not being as effective as random exploration in others. Finally, we demonstrate that random exploration can also improve the coverage of LAMA, a planner which already employs multiple enhancements. This suggests that knowledge-based enhancements need to be compared to appropriate knowledge-free random baselines so as to ensure the importance of the knowledge being used.

SoCS Conference 2013 Conference Paper

Optimal-Generation Variants of EPEA

Meir Goldenberg
Ariel Felner
Nathan R. Sturtevant
Robert C. Holte
Jonathan Schaeffer 0001

It is known that A* is optimal with respect to the expanded nodes (Dechter and Pearl 1985) (D&P). The exact meaning of this optimality varies depending on the class of algorithms and instances over which A* is claimed to be optimal. A* does not provide any optimality guarantees with respect to the generated nodes. However, such guarantees may be critical for optimally solving instances of domains with a large branching factor. In this paper, we introduce two new variants of the recently introduced Enhanced Partial Expansion A* algorithm (EPEA*) (Felner et al. 2012). We leverage the results of D&P to show that these variants possess optimality with respect to the generated nodes in much the same sense as A* possesses optimality with respect to the expanded nodes. The results in this paper are theoretical. A study of the practical performance of the new variants is beyond the scope of this paper.

SoCS Conference 2012 Conference Paper

A* Variants for Optimal Multi-Agent Pathfinding

Meir Goldenberg
Ariel Felner
Roni Stern
Jonathan Schaeffer 0001

Several variants of A* have been recently proposed for find-ing optimal solutions for the multi-agent pathfinding (MAPF)problem. We describe the application of the new enhancedpartial-expansion technique to MAPF, show how patterndatabases can be applied on top of this technique and com-pare the different A* variants experimentally.

ECAI Conference 2012 Conference Paper

ArvandHerd: Parallel Planning with a Portfolio

Richard Valenzano
Hootan Nakhost
Martin Müller 0003
Jonathan Schaeffer 0001
Nathan R. Sturtevant

ArvandHerd is a parallel planner that won the multicore sequential satisficing track of the 2011 International Planning Competition (IPC 2011). It assigns processors to run different members of an algorithm portfolio which contains several configurations of each of two different planners: LAMA-2008 and Arvand. In this paper, we demonstrate that simple techniques for using different planner configurations can significantly improve the coverage of both of these planners. We then show that these two planners, when using multiple configurations, can be combined to construct a high performance parallel planner. In particular, we will show that ArvandHerd can solve more IPC benchmark problems than even a perfect parallelization of LAMA-2011, which won the satisficing track at IPC 2011. We will also show that the coverage of ArvandHerd can be further improved if LAMA-2008 is replaced by LAMA-2011 in the portfolio.

SoCS Conference 2012 Conference Paper

Partial-Expansion A* with Selective Node Generation

Ariel Felner
Meir Goldenberg
Guni Sharon
Roni Stern
Tal Beja
Nathan R. Sturtevant
Robert C. Holte
Jonathan Schaeffer 0001

A* is often described as being 'optimal, ' in that it expands the minimum number of unique nodes. But, A* may generate many extra nodes which are never expanded. This is a performance loss, especially when the branching factor is large. Partial Expansion A* (PEA*) addresses this problem when expanding a node, n, by generating all the children of n but only storing children with the same f-cost as n. We introduce an enhanced version of PEA* (EPEA*). Given a priori domain knowledge, EPEA* only generates the children with the same f-cost as the parent. State-of-the-art results were obtained for a number of domains. Drawbacks of EPEA* are also discussed. A full version of this paper appears in the proceedings of AAAI-2012

SoCS Conference 2011 Conference Paper

Abstract: Block A* and Any-Angle Path-Planning

Peter Kai Yue Yap
Neil Burch
Robert C. Holte
Jonathan Schaeffer 0001

We present three new ideas for grid-based path-planning algorithms that improve the search speed and quality of the paths found. First, we introduce a new type of database, the Local Distance Database (LDDB), that contains distances between boundary points of a local neighborhood. Second, an LDDB-based algorithm is introduced, called Block A*, that calculates the optimal path between start and goal locations given the local distances stored in the LDDB. Third, our experimental results for any-angle path planning in a wide varietyof test domains, including real game maps, show that Block A* is faster than both A* and the previously best grid-based any-angle search algorithm, Theta*.

SoCS Conference 2011 Conference Paper

Degrees of Separation in Social Networks

Reza Bakhshandeh
Mehdi Samadi
Zohreh Azimifar
Jonathan Schaeffer 0001

Social networks play an increasingly important role in today

SoCS Conference 2011 Conference Paper

The Compressed Differential Heuristic

Meir Goldenberg
Nathan R. Sturtevant
Ariel Felner
Jonathan Schaeffer 0001

The differential heuristic (DH) is an effective memory-based heuristic for explicit state spaces. In this paper, we aim to improve its performance and memory usage. We introduce a compression method for DHs which stores only a portion of the original uncompressed DH, while preserving enough information to enable efficient search. Compressed DHs (CDH) can be tuned to fit any size of memory, even smaller than the size of the state space. Experimental results across different domains show that, for a given amount of memory, a CDH significantly outperforms an uncompress

ECAI Conference 2010 Conference Paper

Automating Layouts of Sewers in Subdivisions

Neil Burch
Robert C. Holte
Martin Müller 0003
David O'Connell
Jonathan Schaeffer 0001

An important part of the creation of a housing subdivision is the design and layout of sewers underneath the road. This is a challenging cost optimization problem in a continuous threedimensional space. In this paper, heuristic-search-based techniques are proposed for tackling this problem. The result is new algorithms that can quickly find near optimal solutions that offer important reductions in the cost of design and construction.

SoCS Conference 2010 Conference Paper

Portal-Based True-Distance Heuristics for Path Finding

Meir Goldenberg
Ariel Felner
Nathan R. Sturtevant
Jonathan Schaeffer 0001

True distance memory-based heuristics (TDHs) were recently introduced as a way to obtain admissible heuristics for explicit state spaces. In this paper, we introduce a new TDH, the portal-based heuristic. The domain is partitioned into regions and portals between regions are identified. True distances between all pairs of portals are stored and used to obtain admissible heuristics throughout the search. We introduce an A*-based algorithm that takes advantage of the special properties of the new heuristic. We study the advantages and limitations of the new heuristic. Our experimental results show large performance improvements over previously-reported TDHs for commonly used classes of maps.

SoCS Conference 2010 Conference Paper

Simultaneously Searching with Multiple Settings: An Alternative to Parameter Tuning for Suboptimal Single-Agent Search Algorithms

Richard Valenzano
Nathan R. Sturtevant
Jonathan Schaeffer 0001
Karen Buro
Akihiro Kishimoto

Many search algorithms have parameters that need to be tuned to get the best performance. Typically, the parameters are tuned offline, resulting in a generic setting that is supposed to be effective on all problem instances. For suboptimal single-agent search, problem-instance-specific parameter settings can result in substantially reduced search effort. We consider the use of dovetailing as a way to take advantage of this fact. Dovetailing is a procedure that performs search with multiple parameter settings simultaneously. Dovetailing is shown to improve the search speed of weighted IDA* by several orders of magnitude and to generally enhance the performance of weighted RBFS. This procedure is trivially parallelizable and is shown to be an effective form of parallelization for WA* and BULB. In particular, using WA* with parallel dovetailing yields good speedups in the sliding-tile puzzle domain, and increases the number of problems solved when used in an automated planning system.

ICAPS Conference 2010 Conference Paper

Simultaneously Searching with Multiple Settings: An Alternative to Parameter Tuning for Suboptimal Single-Agent Search Algorithms

Richard Valenzano
Nathan R. Sturtevant
Jonathan Schaeffer 0001
Karen Buro
Akihiro Kishimoto

Many search algorithms have parameters that need to be tuned to get the best performance. Typically, the parameters are tuned offline, resulting in a generic setting that is supposed to be effective on all problem instances. For suboptimal single-agent search, problem-instance-specific parameter settings can result in substantially reduced search effort. We consider the use of dovetailing as a way to take advantage of this fact. Dovetailing is a procedure that performs search with multiple parameter settings simultaneously. Dovetailing is shown to improve the search speed of weighted IDA* by several orders of magnitude and to generally enhance the performance of weighted RBFS. This procedure is trivially parallelizable and is shown to be an effective form of parallelization for WA* and BULB. In particular, using WA* with parallel dovetailing yields good speedups in the sliding-tile puzzle domain, and increases the number of problems solved when used in an automated planning system.

SoCS Conference 2010 Conference Paper

Single-Frontier Bidirectional Search

Carsten Moldenhauer
Ariel Felner
Nathan R. Sturtevant
Jonathan Schaeffer 0001

We introduce a new bidirectional search algorithm, Single-Frontier Bidirectional Search (SFBDS). Unlike traditional BDS which keeps two frontiers, SFBDS uses a single frontier. At a particular node we can decide to search from start to goal or from goal to start, choosing the direction with the highest potential for minimizing the total work done. We provide theoretical analysis that explains when SFBDS will work validated by experimental results.

ECAI Conference 2008 Conference Paper

Using abstraction in Two-Player Games

Mehdi Samadi
Jonathan Schaeffer 0001
Fatemeh Torabi Asr
Majid Samar
Zohreh Azimifar

For most high-performance two-player game programs, a significant amount of time is devoted to developing the evaluation function. An important issue in this regard is how to take advantage of a large memory. For some two-player games, endgame databases have been an effective way of reducing search effort and introducing accurate values into the search. For some one-player games (puzzles), pattern databases have been effective at improving the quality of the heuristic values used in a search.

ICAPS Conference 2007 Conference Paper

Dynamic Control in Path-Planning with Real-Time Heuristic Search

Vadim Bulitko
Yngvi Björnsson
Mitja Lustrek
Jonathan Schaeffer 0001
Sverrir Sigmundarson

Real-time heuristic search methods, such as LRTA*, are used by situated agents in applications that require the amount of planning per action to be constant-bounded regardless of the problem size. LRTA* interleaves planning and execution, with a fixed search depth being used to achieve progress towards a fixed goal. Here we generalize the algorithm to allow for a dynamically changing search depth and a dynamically changing (sub-)goal. Evaluation in path-planning on video-game maps shows that the new algorithm significantly outperforms fixed-depth, fixed-goal LRTA*. The new algorithm can achieve the same quality solutions as LRTA*, but with nine times less computation, or use the same amount of computation, but produce four times better quality solutions. These extensions make real-time heuristic search a practical choice for path-planning in computer video-games.

ICAPS Conference 2005 Conference Paper

Learning Partial-Order Macros from Solutions

Adi Botea
Martin Müller 0003
Jonathan Schaeffer 0001

Despite recent progress in AI planning, many problems remain challenging for current planners. In many domains, the performance of a planner can greatly be improved by discovering and exploiting information about the domain structure that is not explicitly encoded in the initial PDDL formulation. In this paper we present an automated method that learns relevant information from previous experience in a domain and uses it to solve new problem instances. Our approach produces a small set of useful macro-operators as a result of a training process. For each training problem, a structure called a solution graph is built based on the problem solution. Macro-operators with partial ordering of moves are extracted from the solution graph. A filtering and ranking procedure selects the most useful macro-operators, which will be used in future searches. We introduce a heuristic technique that uses only the most promising instantiations of a selected macro for node expansion. Our results indicate an impressive reduction of the search effort in complex domains where structure information can be inferred.

ICAPS Conference 2004 Conference Paper

Using Component Abstraction for Automatic Generation of Macro-Actions

Adi Botea
Martin Müller 0003
Jonathan Schaeffer 0001

Despite major progress in AI planning over the last few years, many interesting domains remain challenging for current planners. This paper presents component abstraction, an automatic and generic technique that can reduce the complexity of an important class of planning problems. Component abstraction uses static facts in a problem definition to decompose the problem into linked abstract components. A local analysis of each component is performed to speed up planning at the component level. Our implementation uses this analysis to statically build macro operators specific to each component. A dynamic filtering process keeps for future use only the most useful macro operators. We demonstrate our ideas in Depots, Satellite, and Rovers, three standard domains used in the third AI planning competition. Our results show an impressive potential for macro operators to reduce the search complexity and achieve more stable performance.