We describe an approximate dynamic programming algorithm for partially observable Markov decision processes represented in factored form. Two complementary forms of approximation are used to simplify a piecewise linear and convex value function, where each linear facet of the function is represented compactly by an algebraic decision diagram. ln one form of approximation, the degree of state abstraction is increased by aggregating states with similar values. In the second form of approximation, the value function is simplified by removing linear facets that contribute marginally to value. We derive an error bound that applies to both forms of approximation. Experimental results show that this approach improves the performance of dynamic programming and extends the range of problems it can solve.

Property Directed Reachability (PDR), also known as IC3, is a very promising recent method for deciding reachability in symbolically represented transition systems. While originally conceived as a model checking algorithm for hardware circuits, it has already been successfully applied in several other areas. This paper summarizes the first investigation of PDR from the perspective of automated planning.

This work combines recent advances in AI planning under memory limitation, namely bitvector and symbolic search. Bitvector search assumes a bijective mapping between state and memory addresses, while symbolic search compactly represents state sets. The memory requirements vary with the structure of the problem to be solved. The integration of the two algorithms into one hybrid algorithm for strongly solving general games initiates a BDD-based solving algorithm, which consists of a forward computation of the reachable state set, possibly followed by a layered backward retrograde analysis. If the main memory becomes exhausted, it switches to explicit-state two-bit retrograde search. We use the classical game of Connect Four as a case study, and solve some instances of the problem space-efficiently with the proposed hybrid search algorithm.

Multiagent path planning is important in a variety of fields, ranging from games to robotics and warehouse management. Although centralized control in the joint action space can provide optimal plans, this often is computationally infeasi- ble. Decoupled planning is much more scalable. Traditional decoupled approaches perform a unit-centric decomposition, replacing a multi-agent search with a series of single-agent searches, one for each mobile unit. We introduce an orthogonal, significantly different approach, following a spatial distribution that partitions a map into high- contention, bottleneck areas and low-contention areas. Lo- cal agents called controllers are in charge with one local area each, routing mobile units in their corresponding area. Dis- tributing the knowledge across the map, each controller can observe only the state of its own area. Adjacent controllers can communicate to negotiate the transfer of mobile units. We evaluate our implemented algorithm, SDP, on real game maps with a mixture of larger areas and narrow, bottleneck gateways. The results demonstrate that spatially distributed planning can have substantial benefits in terms of makespan quality and computation speed.

Finding the shortest plan for a given planning problem is extremely hard. We present a domain independent approach for plan optimisation based on Genetic Programming. The algorithm is seeded with correct plans created by hand-encoded heuristic policy sets. The plans are very unlikely to be optimal but are created quickly. The suboptimal plans are then evolved using a generational algorithm towards the optimal plan. We present initial results from Blocks World and found that GP method almost always improved sub-optimal plans, often drastically.

The Disjunctive Temporal Problem (DTP) involves the satisfaction of aset of constraints represented by disjunctive formulas of the form x 1 - y 1 <= r 1 or x 2 - y 2 <= r 2 or ... or x k - y k <= r k . DTP is a  general temporal reasoning problem which includes the well-known Temporal Constraint Satisfaction Problem (TCSP) introduced by Dechter, Meiri and Pearl. This paper describes a basic constraint satisfaction algorithm where several aspects of the current literature are integrated, in particular the so-called incremental forward checking.  Hence,two new extended solving strategies are proposed and experimentally evaluated. The new proposed strategies are very competitive with the best results available in the current literature. In addition, the analysis of the empirical results suggests future research directions concerning in particular the use of arc-consistency filtering strategies.

Most current planners assume complete domain models and focus on generating correct plans. Unfortunately, domain modeling is a laborious and error-prone task, thus real world agents have to plan with incomplete domain models. While domain experts cannot guarantee completeness, often they are able to circumscribe the incompleteness of the model by providing annotations as to which parts of the domain model may be incomplete. In this paper, we study planning problems with incomplete STRIPS domain models where the annotations specify possible preconditions and effects of actions. We show that the problem of assessing the quality of a plan, or its plan robustness, is #P-complete, establishing its equivalence with the weighted model counting problems. We introduce two approximations, lower and upper bound, for plan robustness, and then utilize them to derive heuristics for synthesizing robust plans. Our planning system, PISA, incorporating stochastic local search with these novel techniques outperforms a state-of-the-art planner handling incomplete domains in most of the tested domains, both in terms of plan quality and planning time.

Many known planning tasks have inherent constraints concerning the best order in which to achieve the goals. A number of research efforts have been made to detect such constraints and use them for guiding search, in the hope to speed up the planning process. We go beyond the previous approaches by defining ordering constraints not only over the (top level) goals, but also over the sub-goals that will arise during planning. Landmarks are facts that must be true at some point in every valid solution plan. We show how such landmarks can be found, how their inherent ordering constraints can be approximated, and how this information can be used to decompose a given planning task into several smaller sub-tasks. Our methodology is completely domain- and planner-independent. The implementation demonstrates that the approach can yield significant performance improvements in both heuristic forward search and Graphplan-style planning.

Several real world applications require planners that deal with  non-deterministic domains and with temporally extended goals. Recent  research is addressing this planning problem. However, the ability  of dealing in practice with large state spaces is still an open  problem. In this paper we describe a planning algorithm for extended goals  that makes use of BDD-based symbolic model checking  techniques. We implement the algorithm in the MBP planner,  evaluate its applicability experimentally, and compare it with  existing tools and algorithms. The results show that, in spite of the difficulty of the problem, MBP deals in practice with domains of large size and with  goals of a certain complexity.

This paper addresses the challenge of efficiently and accurately predicting an electric vehicle's attainable range. Specifically, our approach accounts for a driver's generalised route preferences to provide up-to-date, personalised information based on estimates of the energy required to reach every possible destination in a map. We frame this task in the context of sequential decision making and show that energy consumption in reaching a particular destination can be formulated as policy evaluation in a Markov Decision Process. In particular, we exploit the properties of the model adopted for predicting likely energy consumption to every possible destination in a realistically sized map in real-time. The policy to be evaluated is learned and, over time, refined using Inverse Reinforcement Learning to provide for a life-long adaptive system. Our approach is evaluated using a publicly available dataset providing real trajectory data of 50 individuals spanning approximately 10,000 miles of travel. We show that by accounting for driver specific route preferences our system significantly reduces the relative error in energy prediction compared to more common, driver-agnostic heuristics such as shortest-path or shortest-time routes.