Bonet, Blai


A Summary of the Twenty-Ninth AAAI Conference on Artificial Intelligence

AI Magazine

The Twenty-Ninth AAAI Conference on Artificial Intelligence, (AAAI-15) was held in January 2015 in Austin, Texas (USA) The conference program was cochaired by Sven Koenig and Blai Bonet. This report contains reflective summaries of the main conference, the robotics program, the AI and robotics workshop, the virtual agent exhibition, the what's hot track, the competition panel, the senior member track, student and outreach activities, the student abstract and poster program, the doctoral consortium, the women's mentoring event, and the demonstrations program.


A Summary of the Twenty-Ninth AAAI Conference on Artificial Intelligence

AI Magazine

The Twenty-Ninth AAAI Conference on Artificial Intelligence, (AAAI-15) was held in January 2015 in Austin, Texas (USA) The conference program was cochaired by Sven Koenig and Blai Bonet. This report contains reflective summaries of the main conference, the robotics program, the AI and robotics workshop, the virtual agent exhibition, the what's hot track, the competition panel, the senior member track, student and outreach activities, the student abstract and poster program, the doctoral consortium, the women's mentoring event, and the demonstrations program.


Policies that Generalize: Solving Many Planning Problems with the Same Policy

AAAI Conferences

We establish conditions under which memoryless policies and finite-state controllers that solve one partially observable non-deterministic problem (PONDP) generalize to other problems; namely, problems that have a similar structure and share the same action and observation space. This is relevant to generalized planning where plans that work for many problems are sought, and to transfer learning where knowledge gained in the solution of one problem is to be used on related problems. We use a logical setting where uncertainty is represented by sets of states and the goal is to be achieved with certainty. While this gives us crisp notions of solution policies and generalization, the account also applies to probabilistic  PONDs, i.e., Goal POMDPs.


Flow-Based Heuristics for Optimal Planning: Landmarks and Merges

AAAI Conferences

We describe a flow-based heuristic for optimal planning that exploits landmarks and merges. The heuristic solves a lin- ear programming (LP) problem that represents variables in SAS+ planning as a set of interacting network flow prob- lems. The solution to the LP provides a reasonable admissible heuristic for optimal planning, but we improve it considerably by adding constraints derived from action landmarks and from variable merges. Merged variables, however, can quickly grow in size and as a result introduce many new variables and constraints into the LP. In order to control the size of the LP we introduce the concept of dynamic merging that allows us to partially and incrementally merge variables, thus avoiding the formation of cross products of domains as done when merging variables in the traditional way. The two types of improvements (action landmarks and variable merges) to the LP formulation are orthogonal and general. We measure the impact on performance for optimal planning of each improvement in isolation, and also when combined, for a sim- ple merge strategy. The results show that the new heuristic is competitive with the current state of the art.


LP-Based Heuristics for Cost-Optimal Planning

AAAI Conferences

Many heuristics for cost-optimal planning are based on linear programming. We cover several interesting heuristics of this type by a common framework that fixes the objective function of the linear program. Within the framework, constraints from different heuristics can be combined in one heuristic estimate which dominates the maximum of the component heuristics. Different heuristics of the framework can be compared on the basis of their constraints. With this new method of analysis, we show dominance of the recent LP-based state-equation heuristic over optimal cost partitioning on single-variable abstractions.  We also show that the previously suggested extension of the state-equation heuristic to exploit safe variables cannot lead to an improved heuristic estimate. We experimentally evaluate the potential of the proposed framework on an extensive suite of benchmark tasks.


An Admissible Heuristic for SAS+ Planning Obtained from the State Equation

AAAI Conferences

Domain-independent optimal planning has seen important breakthroughs in recent years with the development of tractable and informative admissible heuristics, suitable for planners based on forward state-space search. These heuristics allow planners to optimally solve an important number of benchmark problems, including problems that are quite involved and difficult for the layman. In this paper we present a new admissible heuristic that is obtained from the state equation associated to the Petri-net representation of the planning problem. The new heuristic, that does not fall into one of the four standard classes, can be computed in polynomial time and is competitive with the current state of the art for optimal planning, as empirically demonstrated over a large number of problems, mainly because it often shows an improved quality-to-cost ratio. The new heuristic applies to SAS+ planning tasks with arbitrary non-negative action costs.


Causal Belief Decomposition for Planning with Sensing: Completeness Results and Practical Approximation

AAAI Conferences

Belief tracking is a basic problem in planning with sensing. While the problem is intractable, it has been recently shown that for both deterministic and non-deterministic systems expressed in compact form, it can be done in time and space that are exponential in the problem width. The width measures the maximum number of state variables that are all relevant to a given precondition or goal. In this work, we extend this result both theoretically and practically. First, we introduce an alternative decomposition scheme and algorithm with the same time complexity but different completeness guarantees, whose space complexity is much smaller: exponential in the causal width of the problem that measures the number of state variables that are causally relevant to a given precondition, goal, or observable. Second, we introduce a fast, meaningful, and powerful approximation that trades completeness by speed, and is both time and space exponential in the problem causal width. It is then shown empirically that the algorithm combined with simple heuristics yields state-of-the-art real-time performance in domains with high widths but low causal widths such as Minesweeper, Battleship, and Wumpus.


Automatic Reductions from PH into STRIPS or How to Generate Short Problems with Very Long Solutions

AAAI Conferences

Recently, it has been shown how to automatically translate any problem in NP, expressed in the language of second-order logic, into a STRIPS planning problem. In this work, we extend this translation by considering decision problems in the polynomial-time hierarchy (PH) and not just NP. Since decision problems in PH require in general exponentially-long “certificates”, the plans (if any) for the resulting STRIPS problems may have exponential length. Besides explaining the novel translations, we present experimental results and discuss the challenges that such problems pose.


Arguing for Decisions: A Qualitative Model of Decision Making

arXiv.org Artificial Intelligence

We develop a qualitative model of decision making with two aims: to describe how people make simple decisions and to enable computer programs to do the same. Current approaches based on Planning or Decisions Theory either ignore uncertainty and tradeoffs, or provide languages and algorithms that are too complex for this task. The proposed model provides a language based on rules, a semantics based on high probabilities and lexicographical preferences, and a transparent decision procedure where reasons for and against decisions interact. The model is no substitude for Decision Theory, yet for decisions that people find easy to explain it may provide an appealing alternative.


A Calculus for Causal Relevance

arXiv.org Artificial Intelligence

This paper presents a sound and completecalculus for causal relevance, based onPearl's functional models semantics.The calculus consists of axioms and rulesof inference for reasoning about causalrelevance relationships.We extend the set of known axioms for causalrelevance with three new axioms, andintroduce two new rules of inference forreasoning about specific subclasses ofmodels.These subclasses give a more refinedcharacterization of causal models than the one given in Halpern's axiomatizationof counterfactual reasoning.Finally, we show how the calculus for causalrelevance can be used in the task ofidentifying causal structure from non-observational data.