Least Restrictive Supervisors for Intersection Collision Avoidance: A Scheduling Approach

Colombo, Alessandro; Del Vecchio, Domitilla · 2015 · Crossref

DOI: 10.1109/tac.2014.2381453

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper addresses the problem of designing least restrictive supervisors for cooperative conflict resolution in multi-agent systems, specifically focusing on vehicle intersection crossing. The primary motivation is to ensure safety (collision avoidance) while minimizing intervention, allowing agents to retain control unless their actions would compromise safety. Existing methods for determining the maximal controlled invariant set—the largest set of states from which safety can be guaranteed—are often computationally prohibitive, with NP-hard complexity or exponential scaling relative to the number of agents. The authors propose a novel approach that leverages the monotonicity of agent dynamics to translate the verification problem (determining if a safe control exists) into an equivalent scheduling problem, enabling the use of efficient algorithms from scheduling theory. The methodology models agents as point masses moving unidirectionally along specified paths with monotone dynamics. The authors define a verification problem (VP) to determine if there exists an input signal that keeps the system state outside a "bad set" of collisions for all time. They prove that this VP is equivalent to a scheduling problem (SP) involving release times, deadlines, and precedence constraints. By exploiting the structure of the system, they decouple the difficult task of determining the order in which agents cross the intersection from the simpler task of determining how they cross once the order is fixed. The paper provides algorithmic procedures to compute exact solutions and approximate solutions with polynomial complexity. These algorithms utilize the properties of monotone systems to recursively compute maximum input signals that satisfy safety constraints, ensuring guaranteed termination and approximation bounds. The main findings demonstrate that the proposed scheduling-based approach allows for the synthesis of least restrictive supervisors that are computationally efficient enough for real-time application in systems with a large number of agents. Unlike previous methods that scale exponentially or are limited to two-agent scenarios, the proposed approximate algorithms have polynomial complexity. The authors provide tight approximation bounds to quantify the difference between the approximate and exact solutions. Simulations illustrate that the supervisor overrides agent control only when necessary to maintain safety, thereby satisfying the requirement of least restrictiveness. The equivalence proof between the verification problem and the scheduling problem establishes a rigorous theoretical foundation for using scheduling techniques in supervisory control. The significance of this work lies in providing a scalable, computationally efficient framework for safety-critical multi-agent systems. By transforming a complex control problem into a well-studied scheduling problem, the authors enable the practical implementation of least restrictive supervisors in real-world applications such as autonomous vehicle intersection management. The approach ensures safety guarantees while preserving agent autonomy, addressing a key challenge in the deployment of automated driver assist systems. The results contribute to the field of supervisory control by offering a method that balances safety, efficiency, and minimal intervention, with provable performance bounds.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• driver vru interaction