Spatial deadlocks in task-level planning

Abstract

We will formulate the problem of resolving spatial (space occupancy and support-stability) interactions in terms of tools developed in Operating Systems for the problems of deadlocks and synchronization. We show how to construct state graphs and to detect resource contentions and deadlocks from these state graphs. We describe an algorithm, called CONTAC, to deal with deadlocks where 'processes' represent the ordered motions of parts. The algorithm is a monitor-like process using preventative preemptive protocol to resolve higher-degree deadlocks. We develop the representation for knowledge about current allocations, pending requests, and synchronization constraints, to generate a contention-free sequence of actions. In this paper we focus on modeling deadlocks which are manifestations of spatial interactions.