Constructing Conflict-Free Schedules in Space and Time

Abstract

This paper addresses the problem of constructing plans and schedules for resources that must obey spatial constraints in addition to time and capacity constraints. Spatial constraints are relevant in environments that involve mobile resources whose movements must be coordinated to avoid collisions and near-misses. In air-campaign planning, for example, aircraft are allocated to missions that must be flown concurrently within a localized and often heavily populated environment. Mission routes tend to be generated dynamically and must ensure that sufficient spatial separation is maintained at all times among all aircraft. We present a solution to this class of problems that treats the standard resource-allocation problem as a four-dimensional one, where the space in which resources must maneuver is itself managed as a capacitated resource. Underlying our approach is a representation of spatial capacity that uses a linear octree structure for indexing vector-based vehicle routes. Generalizing the notion of contention-based search heuristics, we present an algorithm that first solves a relaxed version of the problem to construct a spatial capacity profile (represented as an octree), and then uses spatio-temporal regions where demand exceeds capacity to make conflict-avoiding vehicle routing and scheduling decisions. To demonstrate the viability of the approach we present experimental results using data from a realistically sized air-campaign planning domain.