Welte , Anthony, Jaulin , Luc, Ceberio , Martine, Kreinovich , Vladik, Lab-STICC_ENSTAB_CID_PRASYS, Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance (Lab-STICC), Institut Mines-Télécom [Paris] (IMT)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-École Nationale d'Ingénieurs de Brest (ENIB)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-Centre National de la Recherche Scientifique (CNRS)-Université Bretagne Loire (UBL)-Institut Mines-Télécom [Paris] (IMT)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-École Nationale d'Ingénieurs de Brest (ENIB)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-Centre National de la Recherche Scientifique (CNRS)-Université Bretagne Loire (UBL), Pôle STIC_OSM, École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne), University of Texas [El Paso] (UTEP ), Laboratoire Chrono-environnement ( LCE ), Université Bourgogne Franche-Comté ( UBFC ) -Centre National de la Recherche Scientifique ( CNRS ) -Université de Franche-Comté ( UFC ), Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance ( Lab-STICC ), École Nationale d'Ingénieurs de Brest ( ENIB ) -Université de Bretagne Sud ( UBS ) -Université de Brest ( UBO ) -ENSTA Bretagne-Institut Mines-Télécom [Paris]-Centre National de la Recherche Scientifique ( CNRS ) -Université Bretagne Loire ( UBL ) -IMT Atlantique Bretagne-Pays de la Loire ( IMT Atlantique ) -École Nationale d'Ingénieurs de Brest ( ENIB ) -Université de Bretagne Sud ( UBS ) -Université de Brest ( UBO ) -ENSTA Bretagne-Institut Mines-Télécom [Paris]-Centre National de la Recherche Scientifique ( CNRS ) -Université Bretagne Loire ( UBL ) -IMT Atlantique Bretagne-Pays de la Loire ( IMT Atlantique ), ENSTA Bretagne, University of Texas at El Paso - UTEP (USA), École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-Université Bretagne Loire (UBL)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-École Nationale d'Ingénieurs de Brest (ENIB)-Université de Bretagne Sud (UBS)-Université de Brest (UBO)-École Nationale Supérieure de Techniques Avancées Bretagne (ENSTA Bretagne)-Institut Mines-Télécom [Paris] (IMT)-Centre National de la Recherche Scientifique (CNRS)-Université Bretagne Loire (UBL)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), and Institut Mines-Télécom [Paris] (IMT)
International audience; 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.