Computability of the Avoidance Set and of the Set-Valued Identification Problem

Anthony Welte , Luc Jaulin (1, 2) , Martine Ceberio (3) , Vladik Kreinovich (3)

1 Lab-STICC_ENSTAB_CID_PRASYS
2 Pôle STIC_OSM
3 UTEP - University of Texas [El Paso]

In some practical situations, we need to find the avoidance set, i.e., the set of all initial states for which the system never goes into the forbidden region. Algorithms are known for computing the avoidance set in several practically important cases. In this paper, we consider a general case, and we show that, in some reasonable sense, the corresponding general problem is always algorithmically solvable. A similar algorithm is possible for another general system-related problem: the problem of describing the set of all possible states which are consistent with the available measurement results. 1 Formulation of the Problem In control, we usually deal with robots (or other controlled devices) whose states s are described by tuples of real numbers s = (s 1 , · · · , s d). The dynamics of such devices is usually described by a system of differential equations ds i dt = f i (s(t)), for a known computable functions f i (s). In most practical situations, we can use these equations to compute, for each initial state s 0 at the starting moment t 0 , and for each moment of time t < t 0 , the state s(s 0 , t) of the system at the moment t; see, e.g., [2, 4, 10, 12]. Often in control, we have a set S of states that a robot (or other controlled device) needs to avoid. Because of this necessity: • once we know how the states change in time, i.e., once we know the algorithm s(t, s 0) that describes how the state s at moment t depends on t and on the initial state s 0 , • we need to find the set S 0 of all the initial states for which the trajectory avoids the forbidden set S for all moments of time from the starting moment t 0 to a given future moment T. In other words, we want to find the avoidance set S 0 = {s 0 : s(t, s 0) ̸ ∈ S for all t ∈ [t 0 , T ]}. There exist algorithms for solving this problem in some specific situations; see, e.g., [3, 7, 9]. In this paper, we analyze the general problem of computing the avoidance set, and we show that this problem is, in some reasonable sense, algorithmically computable.

Mots clés: avoidance set; set-valued uncertainty; computability; forbidden region

Domaines: Robotique [cs.RO]; Systèmes dynamiques [math.DS]; Automatique / Robotique; Intelligence artificielle [cs.AI]

Anthony Welte, Luc Jaulin, Martine Ceberio, Vladik Kreinovich. Computability of the Avoidance Set and of the Set-Valued Identification Problem. Journal of Uncertain Systems, 2017, 11, pp.129 - 136. ⟨hal-01698372⟩