https://hal-ensta-bretagne.archives-ouvertes.fr/hal-01698372Welte, AnthonyAnthonyWelteJaulin, LucLucJaulinLab-STICC_ENSTAB_CID_PRASYS - Lab-STICC - Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance - ENIB - École Nationale d'Ingénieurs de Brest - UBS - Université de Bretagne Sud - UBO - Université de Brest - ENSTA Bretagne - École Nationale Supérieure de Techniques Avancées Bretagne - IMT - Institut Mines-Télécom [Paris] - CNRS - Centre National de la Recherche Scientifique - UBL - Université Bretagne Loire - IMT Atlantique - IMT Atlantique - IMT - Institut Mines-Télécom [Paris]Pôle STIC_OSM - ENSTA Bretagne - École Nationale Supérieure de Techniques Avancées BretagneCeberio, MartineMartineCeberioUTEP - University of Texas [El Paso]Kreinovich, VladikVladikKreinovichUTEP - University of Texas [El Paso]Computability of the Avoidance Set and of the Set-Valued Identification ProblemHAL CCSD2017avoidance setset-valued uncertaintycomputabilityforbidden region[INFO.INFO-RB] Computer Science [cs]/Robotics [cs.RO][MATH.MATH-DS] Mathematics [math]/Dynamical Systems [math.DS][SPI.AUTO] Engineering Sciences [physics]/Automatic[INFO.INFO-AI] Computer Science [cs]/Artificial Intelligence [cs.AI]Briec, Marie2018-02-02 11:20:492023-03-24 14:53:062018-02-05 14:12:14enJournal articlesapplication/pdf1In 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.