Planning with process algebraic constraints: Application to multi-vehicle routing problem

We present an efficient planning algorithm for allocation and scheduling of spatially distributed tasks to multiple heterogenous resources (e.g. mobile sensors, robots) in presence of ordering constraints on task execution and environmental uncertainties. We use Process Algebra (PA) for capturing such constraints. Building on probabilistic timed PA semantics, we define a planning system in form of a transition system, capturing ordering and resource constraints, occurrence of uncontrollable events, task priorities and preemption, and task allocation/scheduling objectives represented as a cost function. We develop an anytime branch and bound algorithm to efficiently search this transition system, and compute optimal strategies which prescribe task allocation and schedules in response to all possible outcomes of uncontrollable events. Several examples are presented and results from numerical simulation of a vehicle routing problem are discussed.