Long Distance Mutual Exclusion (Londex)
- A reasoning tool for
STRIPS planning
Yixin Chen, Ruoyun Huang, Xing Zhao, and Weixiong Zhang
Introduction
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.
londex Linux executable: londex X86-64 londex X86-32
Uncompress the executable files
To run londex
Usage: londex -o domain_file -f problem_file
Output
The output is of the following format, consisting of fact distances and action
distances: