This work proposes new approaches to contingent planning using alternative belief state representations extended from those in conformant planning and a new AND/OR forward search algorithm, called PrAO, for contingent solutions. Each representation was implemented in a new contingent planner. The important role of belief state representation has been confirmed by the fact that our planners all outperform other stateof- the-art planners on most benchmarks and the comparison of their performances varies across all the benchmarks even using the same search algorithm PrAO and same unsophisticated heuristic scheme. The work identifies the properties of each representation method that affect the performance.

Logic, and declarative representation of knowledge in general, have long been a preferred framework for problem solving in AI. However, specific subareas of AI have been eager to abandon general-purpose knowledge representation in favor of methods that seem to address their computational core problems better. In planning, for example, state-space search has in the last several years been preferred to logic-based methods such as SAT. In our recent work, we have demonstrated that the observed performance differences between SAT and specialized state-space search methods largely go back to the difference between a blind (or at least planning-agnostic) and a planning-specific search method. If SAT search methods are given even simple heuristics which make the search goal-directed, the efficiency differences disappear.

Let h be a heuristic function selected for expansions when GBFS with the FF heuristic that estimates the distance to a goal from a node n. GBFS (Hoffmann and Nebel 2001) solves a planning problem. The selects the best node n with the smallest h(n) in the open list horizontal axis indicates each expansion of the best node that maintains nodes that have been generated but have not n in the open list and the vertical axis represents n's corresponding been expanded yet. It then expands n to generate n's successors, heuristic value for that expansion. Circles, the and saves these successors in the open list, unless triangle, and diamond represent expanding nodes that are they have been previously added to the open list.

Agents in highly dynamic adversarial domains, such as RTS games, must continually make time-critical decisions to adapt their behaviour to the changing environment. In such a context, the planning agent must consider his opponent's actions as uncontrollable, or at best influenceable. In general nondeterministic domains where there is no clear turn-taking protocol, most heuristic search methods to date do not explicitly reason about the opponent's actions when guiding the state space exploration towards goal or high-reward states. In contrast, we are investigating a domain-independent heuristic planning approach which reasons about the dynamics and uncontrollability of the opponent's behaviours in order to provide better guidance to the search process of the planner. Our planner takes as input the opponent's behaviours recognized by a plan recognition module and uses them to identify opponent's actions that lead to low-utility projected states. We believe such explicit heuristic reasoning about the potential behaviours of the opponent is crucial when planning in adversarial domains, yet is missing in today's planning approaches.

Plants can have positive effects on each other in numerous ways, including protection from harsh environmental conditions. This phenomenon, known as facilitation, occurs in water-stressed environments when shade from larger shrubs protects smaller annuals from harsh sun, enabling them to exist on scarce water. The topic of this paper is a model of this phenomenon that allows search algorithms to find residential landscape designs that incorporate facilitation to conserve water. This model is based in botany; it captures the growth requirements of real plant species in a fitness function, but also includes a penalty term in that function that encourages facilitative interactions with other plants on the landscape. To evaluate the effectiveness of this approach, two search strategies--simulated annealing and agent-based search--were applied to models of different collections of simulated plant types and landscapes with different light distributions. These two search strategies produced landscape designs with different spatial distributions of the larger plants. All designs exhibited facilitation and lower water use than designs where facilitation was not included.

General Game Players (GGPs) are programs which can play an arbitrary game given only its rules and the Game Description Language (GDL) is a variant of Datalog used in GGP competitions to specify the rules. GDL inherits from Datalog the use of Horn clauses as rules and recursion, but it too requires stratification and does not allow to use quantifiers. We present an alternative formalism for game description which is based on first-order logic (FO). States of the game are represented by relational structures, legal moves by structure rewriting rules guarded by FO formulas, and the goals of the players by formulas which extend FO with counting. The advantage of our formalism comes from more explicit state representationcand from the use of quantifiers in formulas. We show how to exploit existential quantification in players' goals to generate heuristics for evaluating positions in the game. The derived heuristics are good enough for a basic alpha-beta agent to win against state of the art GGP.

Much recent work in satisficing planning has aimed at striking a balance between coverage - solving as many problems as possible - and plan quality. Current planners achieve near perfect coverage on the latest IPC benchmarks. It is therefore natural to investigate their scaling behavior on more difficult instances. Among state of the art planners, LAMA (Richter, Helmert, and Westphal 2008) is able to generate high quality plans, but its coverage drops off rapidly with increasing prob- lem complexity. The Arvand planner (Nakhost and Müller 2009) scales to much harder instances but generates lower quality plans. This paper introduces a new algorithm, Monte Carlo Random Walk-based Local Tree Search (MRW-LTS), which uses random walks to selectively build local search trees. Experiments demonstrate that MRW-LTS combines a scaling behavior that is better than LAMA’s with a plan quality that is better than Arvand’s.

The rectangle-packing problem consists of finding an enclosing rectangle of smallest area that can contain a given set of rectangles without overlap. Our new benchmark includes rectangles of successively higher precision, challenging the previous state-of-the-art, which enumerates all locations for placing rectangles, as well as all bounding box widths and heights up to the optimal box. We instead limit the rectangles’ coordinates and bounding box dimensions to the set of subset sums of the rectangles’ dimensions. We also dynamically prune values by learning from infeasible subtrees and constrain the problem by replacing rectangles and empty space with larger rectangles. Compared to the previous state-of-the-art, we test 4,500 times fewer bounding boxes on the high-precision benchmark and solve N =9 over two orders of magnitude faster. We also present all optimal solutions up to N =15, which requires 39 bits of precision to solve. Finally, on the open problem of whether or not one can pack a particular infinite series of rectangles into the unit square, we pack the first 50,000 such rectangles witha greedy heuristic and conjecture that the entire infinite series can fit..

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) are flexible and can be tuned to fit any size of memory, even smaller than the size of the state space. Furthermore, CDHs can be built without the need to create and store the entire uncompressed DH. Experimental results across different domains show that, for a given amount of memory, a CDH significantly outperforms an uncompressed DH.

We pose the problem of constructing good search heuristics as an optimization problem: minimizing the loss between the true distances and the heuristic estimates subject to admissibility and consistency constraints. For a well-motivated choice of loss function, we show performing this optimization is tractable. In fact, it corresponds to a recently proposed method for dimensionality reduction. We prove this optimization is guaranteed to produce admissible and consistent heuristics, generalizes and gives insight into differential heuristics, and show experimentally that it produces strong heuristics on problems from three distinct search domains.