Construction of the Solvability Set in Differential Games with Simple Motion and Nonconvex Terminal Set

Abstract

We consider planar zero-sum differential games with simple motion, fixed terminal time, and polygonal terminal set. The geometric constraint on the control of each player is a convex polygonal set or a line segment. In the case of a convex terminal set, an explicit formula is known for the solvability set (a level set of the value function, maximal u-stable bridge, viability set). The algorithm corresponding to this formula is based on the set operations of algebraic sum and geometric difference (the Minkowski difference). We propose an algorithm for the exact construction of the solvability set in the case of a nonconvex polygonal terminal set. The algorithm does not involve the additional partition of the time interval and the recovery of intermediate solvability sets at additional instants. A list of half-spaces in the three-dimensional space of time and state coordinates is formed and processed by a finite recursion. The list is based on the polygonal terminal set with the use of normals to the polygonal constraints on the controls of the players.