We consider a cooperative conflict resolution problem that finds application, for example, in vehicle intersection crossing. We seek to determine minimally restrictive supervisors, which allow agents to choose all possible control actions that keep the system safe, that is, conflict free. This is achieved by determining the maximal controlled invariant set, and then by determining control actions that keep the system state inside this set. By exploiting the natural monotonicity of the agents dynamics along their paths, we translate this problem into an equivalent scheduling problem. This allows us to leverage existing results in the scheduling literature to obtain both exact and approximate solutions. The approximate algorithms have polynomial complexity and can handle large problems with guaranteed approximation bounds. We illustrate the application of the proposed algorithms through simulations in which vehicles crossing an intersection are overridden by the supervisor only when necessary to maintain safety.
A vector field is piecewise smooth if its value jumps across a hypersurface, and a two-fold singularity is a point where the flow is tangent to the hypersurface from both sides. Two-folds are generic in piecewise smooth systems of three or more dimensions. We derive the local dynamics of all possible two-folds in three dimensions, including nonlinear effects around certain bifurcations, finding that they admit a flow exhibiting chaotic but nondeterministic dynamics. In cases where the flow passes through the two-fold, upon reaching the singularity it is unique in neither forward nor backward time, meaning the causal link between inward and outward dynamics is severed. In one scenario this occurs recurrently. The resulting flow makes repeated, but nonperiodic, excursions from the singularity, whose path and amplitude is not determined by previous excursions. We show that this behavior is robust and has many of the properties associated with chaos. Local geometry reveals that the chaotic behavior can be eliminated by varying a single parameter: the angular jump of the vector field across the two-fold.
We consider the problem of synthesising the least restrictive controller for collision avoidance of multiple vehicles at an intersection. The largest set of states for which there exists a control that avoids collisions is known as the maximal controlled invariant set. Exploiting results from the scheduling literature we prove that, for a general model of vehicle dynamics at an intersection, the problem of checking membership in the maximal controlled invariant set is NP-hard. We then describe an algorithm that solves this problem approximately and with provable error bounds. The approximate solution is used to design a supervisor for collision avoidance whose complexity scales polynomially with the number of vehicles. The supervisor is based on a hybrid algorithm that employs a dynamic model of the vehicles and periodically solves a scheduling problem
1 January 2009 in SIAM Journal on Applied Dynamical Systems
When a vector field in $\mathbb{R}^3$ is discontinuous on a smooth codimension one surface, it may be simultaneously tangent to both sides of the surface at generic isolated points (singularities). For a piecewise-smooth dynamical system governed by the vector field, we show that the local dynamics depends on a single quantity—the jump in direction of the vector field through the singularity. This quantity controls a bifurcation, in which the initially repelling singularity becomes the apex of a pair of parabolic invariant surfaces. The surfaces are smooth except where they intersect the discontinuity surface, and they divide local space into regions of attraction to, and repulsion from, the singularity.