Coordination between processing entities is one of the most widely studied areas in multi-agent planning research. Recently, efforts have been made to understand the formal computational issues of this important area. In this paper, we make a step toward this direction, and analyze a certain class of coordination problems for dependent agents with independent goals acting in the same environment. We assume that a state-transition description of each agent is given, and that preconditioning an agent's transitions by the states of other agents is the only considered kind of inter-agent dependence. Off-line coordination between the agents is considered. We analyze some structural properties of these problems, and investigate the relationship between these properties and the complexity of coordination in this domain. We show that our general problem is provably intractable, but some significant subclasses are in NP and even polynomial.

Searching for computational tools that can further push the boundary of satisficing planning, we show that reasoning about state-space symmetries can substantially improve even the most effective heuristic-search satisficing planners, with respect to all standard performance measures. The improvement comes from the state-space pruning, as well as from transparent cost-to-state updates and heuristic enhancement by information obtained during the search at different symmetric states.

List of organizers of the Twenty-First International Conference on Automated Planning and Scheduling, held in Freiburg, Germany, on June 11–16, 2011.

Several recent heuristics for domain independent planning adopt some action cost partitioning scheme to derive admissible heuristic estimates. Given a state, two methods for obtaining an action cost partitioning have been proposed: optimal cost partitioning, which results in the best possible heuristic estimate for that state, but requires a substantial computational effort, and ad-hoc (uniform) cost partitioning, which is much faster, but is usually less informative. These two methods represent almost opposite points in the tradeoff between heuristic accuracy and heuristic computation time. One compromise that has been proposed between these two is using an optimal cost partitioning for the initial state to evaluate all states. In this paper, we propose a novel method for deriving a fast, informative cost-partitioning scheme, that is based on computing optimal action cost partitionings for a small set of states, and using these to derive heuristic estimates for all states. Our method provides greater control over the accuracy/computation-time tradeoff, which, as our empirical evaluation shows, can result in better performance.

Applications range from the detection of potential all times t 1,...T (m 1)τ. We refer to such a sequence problems (such as an elderly person who has fallen down as a model of the system. Note that these models are in their home) to general monitoring of disease progression nonparametric. Theoretically, under some smoothness assumptions (e.g. in Parkinson's disease), or simply tracking the amount (Takens, 1981), if m is big enough, and τ is not of exercise and physical activity that a person gets. Ideally, a multiple of the period of the system, such a model captures such activities should be monitored as precisely as possible, all the relevant dynamics. However, real data is noisy, but using cheap or easily available devices, and in a way that so nonparametric models of the same activity can have high does not interfere with daily life.

It is well known that there cannot be a single "best" heuristic for optimal planning in general. One way of overcoming this is by combining admissible heuristics (e.g. by using their maximum), which requires computing numerous heuristic estimates at each state. However, there is a tradeoff between the time spent on computing these heuristic estimates for each state, and the time saved by reducing the number of expanded states. We present a novel method that reduces the cost of combining admissible heuristics for optimal search, while maintaining its benefits. Based on an idealized search space model, we formulate a decision rule for choosing the best heuristic to compute at each state. We then present an active online learning approach for that decision rule, and employ the learned model to decide which heuristic to compute at each state. We evaluate this technique empirically, and show that it substantially outperforms each of the individual heuristics that were used, as well as their regular maximum.

PCS is a CSP solver that can produce a machine-checkable deductive proof in case it decides that the input problem is unsatisfiable. The roots of the proof may be nonclausal constraints, whereas the rest of the proof is based on resolution of signed clauses, ending with the empty clause. PCS uses parameterized, constraint-specific inference rules in order to bridge between the nonclausal and the clausal parts of the proof. The consequent of each such rule is a signed clause that is 1) logically implied by the nonclausal premise, and 2) strong enough to be the premise of the consecutive proof steps. The resolution process itself is integrated in the learning mechanism, and can be seen as a generalization to CSP of a similar solution that is adopted by competitive SAT solvers.

Recently, Brafman and Engel (2009) proposed new concepts of marginal and conditional utility that obey additive analogues of the chain rule and Bayes rule, which they employed to obtain a directed graphical model of utility functions that resembles Bayes nets. In this paper we carry this analogy a step farther by showing that the notion of utility independence, built on conditional utility, satisfies identical properties to those of probabilistic independence. This allows us to formalize the construction of graphical models for utility functions, directed and undirected, and place them on the firm foundations of Pearl and Paz's axioms of semi-graphoids. With this strong equivalence in place, we show how algorithms used for probabilistic reasoning such as Belief Propagation (Pearl 1988) can be replicated to reasoning about utilities with the same formal guarantees, and open the way to the adaptation of additional algorithms.

Connecting between standard AI planning constructs and a classical cooperative model of transferable-utility coalition games, we introduce the notion of transferable-utility (TU) planning games. The key representational property of these games is that coalitions are valued implicitly based on their ability to carry out efficient joint plans. On the side of the expressiveness, we show that existing succinct representations of monotonic TU games can be efficiently compiled into TU planning games. On the side of computation, TU planning games allow us to provide some of the strongest to date tractability results for core-existence and core-membership queries in succinct TU coalition games.

Abstractions and landmarks are two powerful mechanisms for devising admissible heuristics for classical planning. Here we aim at putting them together by integrating landmark information into abstractions, and propose a concrete realization of this direction suitable for structural-pattern abstractions, as well as for other abstraction heuristics. Our empirical evaluation shows that landmark information can substantially improve the quality of abstraction heuristic estimates.