Long Distance Mutual Exclusion (Londex)
- A reasoning tool for
The concept of mutual exclusion (mutex) has been vital to the recent advances in automated planning and led to many fast planners. Despite the breakthrough brought by mutex, a major limitation of mutex is that it can only detect pairs of actions that cannot happen at the same planning time step or pairs of facts that cannot be valid at the same time step. However, constraints across multiple time steps are ubiquitous in almost all planning domains. For example, in transportation planning, two actions requiring to use the same vehicle but at different locations cannot have execution times that are too close to each other since the vehicle has to be relocated after the first action.
We propose a fundamentally new class of mutual exclusions that significantly generalizes mutex and can be efficiently computed. The proposed long-distance mutual exclusion (londex) can capture constraints over actions and facts not only at the same planning time step but also across multiple time steps. Being a strict generalization of mutex, Londex is much richer and stronger than the latter, and provides a general tool to improve planning efficiency. As an application, we have incorporated londex in SATPLAN04, a leading optimal STRIPS planner. Our experimental results show that londex can provide strong pruning power, resulting in tremendous reduction of planning time, on both STRIPS planning and temporal planning. One of our londex-based planners, MaxPlan, has won the First Place Award in the Optimization Track of the 5th International Planning Competition.
Londex constraints are automatically generated based on a multi-valued domain formulation (MDF) and a domain transition graph (DTG) analysis for propositional planning. Please refer to our IJCAI-07 paper for technical details of the generation algorithm.
Software download: Source Code. The software can be used to preprocess any STRIPS planning domain and will output the londex constraints between facts and actions.