Collaborative Constraint-Based Planning (CCBP)

We will develop the first human-in-the-loop planning system that is fully based on constraint programming (CP). Our system will use novel CP-based techniques for finding plans and allow users to easily specify their plan preferences and domain knowledge in order to iteratively refine the returned plans to their liking. Furthermore, our project will strengthen the connection between planning and constraint programming by transporting ideas between the two research areas.

Classical planning is one of the original core AI research areas. It is the challenge of finding a sequence of actions that transforms a given initial situation into one that satisfies a given goal description. In optimal classical planning, the found plan must minimize the sum of its action costs, in satisficing planning, any plan is fine, but cheaper plans are preferred. Most of today's strongest planners are based on state-space search with goal distance estimators, called heuristics. The predominant algorithms are greedy best-first search for satisficing planning and A* for optimal planning.

In our project, we will leave the beaten path of state-space search planning and tackle the research challenge of solving planning tasks with constraint programming (CP). We do so for reasons of scalability and usability. Regarding scalability, CP provides a flexible framework for combining declarative information, which we will use to let the inference engine reason about global constraints on the solutions for a given planning task. In contrast, state-space search planners can only make local progress towards finding a plan: while they choose actions in sequence, one at a time, in our CP approach the choice of the first action can influence the choice of the last action immediately.

Regarding usability, the CP model makes it very easy for users to specify constraints about desired plans, and to provide domain knowledge. This makes it possible to obtain a human-in-the-loop planning system, where users can iteratively add constraints until the system finds a desirable plan. Passing such information to a state-space search planner would require users to make complicated changes to the task or the planner source code.

PI: Jendrik Seipp

Core team: Damien Van Meerbeeck, Gilles Pesant

Funding: This project is supported by the CUGS Graduate School in Computer Science at Linköping University and the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation.