On the minimax reachability of target sets and target tubes

Abstract

This paper is concerned with the closed-loop control of discrete-time systems in the presence of uncertainty. The uncertainty may arise as disturbances in the system dynamics, disturbances corrupting the output measurements or incomplete knowledge of the initial state of the system. In all cases, the uncertain quantities are assumed unknown except that they lie in given sets. Attention is first given to the problem of driving the system state at the final time into a prescribed target set under the worst possible combination of disturbances. This is then extended to the problem of keeping the entire state trajectory in a given target “tube”. Necessary and sufficient conditions for reachability of a target set and a target tube are given in the case where the system state can be measured exactly, while sufficient conditions for reachability are given for the case when only disturbance corrupted output measurements are available. An algorithm is given for the efficient construction of ellipsoidal approximations to the sets involved, and it is shown that this algorithm leads to linear control laws. The application of the results in this paper to pursuit-evasion games is also discussed. Cet article se rapporte à la commande en boucle fermée de systèmes à temps discret en présence d'incertitudes. L'incertitude peut avoir lieu sous la forme de perturbations dans la dyanmique du système, sous la forme de perturbations faussant les mesures à la sortie ou sous la forme d'une connaissance incomplète de l'état initial du système. Dans tous les cas, les grandeurs incertaines sont supposées inconnues sauf leur appartenance à des séries données. L'article considère d'abord le problème d'amener l'état du système au moment final dans une série préscrite de buts sous la plus mauvaise combinaison de perturbations. Ceci est ensuite généralisé au problème de maintenir toute la trajectoire de l'état à l'intérieur d'une “enveloppe” donnée de buts. L'article donne des conditions nécessaires et suffisantes pour la capacité d'atteindre une série de buts et une enveloppe de buts dans le cas où l'état peut être mesuré exactement, tandis que des conditions suffisantes pour cette capacité d'atteindre sont données lorsque seules des mesures à la sortie faussées par les perturbations sont disponibles. L'article donne un algorithme pour la construction efficace d'approximations elliptiques des séries en question et il est montré que cet algorithme conduit à des lois linéaires de commande. L'article discute également des applications de ces résultats à des jeux de poursuite-fuite. Die Arbeit befaβt sich mit der Regelung von diskontinuierlichen Systemen bei Vorhandensein einer Unbestimmtheit. Sie kann vorliegen in Form von Störungen in der Systemdynamik, von Störungen, die die Ausgangsmessungen fälschen oder von unvollständiger Kenntnis des Anfangszustandes des Systems. In allen Fällen werden die unbestimmten Gröβen als unbekannt, aber als in gegebenen Mengen liegend, angenommen. Betrachtet wird zunächst das Problem der Überführung des Systemzustandes zur Endzeit in eine vorgeschriebene Zielmenge und zwar bei der ungünstigsten Kombination von Störungen. Dies wird auf das Problem der Beschränkung der ganzen Zustandstrajektorie auf einen gegebenen Ziel-“Schlauch” ausgedehnt. Notwendige und hinreichende Bedingungen werden für den Fall angegeben, daβ der Systemzustand exakt gemessen werden kann, während hinreichende Bedingungen für die Erreichbarkeit für den Fall gegeben werden, wenn lediglich durch Störungen gefälschte Messungen vorhanden sind. Angegeben wird ein Algorithmus zur wirksamen Konstruktion von elliptischen Approximationen der enthaltenen Mengen. Weiter wird gezeigt, daβ dieser Algorithmus zu linearen Regelungsgesetzen führt. Die Anwendung der hier gewonnnenen Ergebnisse auf eine Klasse von Verfolgungsspielen wird diskutiert. Hacтoящaя cтaтья oтнocитcя к yпpaвлeнию в зaмкнyтoм кoнтype cиcтeмaми c диcкpeтным вpeмeнeм в пpиcyтcтвии нeoпpeдeлeннocтeй. Heoпpeдeлeннocть мoжeт имeть мecтo в cмыcлe пoмeч в динaмикe cиcтeмы, в cмыcлe пoмeч иcкaжaющич вычoдныe измepeния или в cмыcлe нeпoлнoгo знaния нaчaльнoгo cocтoяния cиcтeмы. Бo вceч cлyчaяч, нeoпpeдeлeнныe вeличины пpeдпoлaгaютcя нeизвecтными зa иcключeниeм ич пpинaдлeжнocти к oпpeдeлeнным pядaм. Cтaтья paccмaтpивaeт cнaчaлa зaдaчy пpивeдeния cocтoяния cиcтeмы в кoнeчный мoмeнт в зaдaнный pяд цeлeй пpи нaичyдшeм coчeтaнии пoмeч. Этo зaтeм oбoбщaeтcя к зaдaчe пoддepжaния cocтoяния внyтpи дaннoй “oбoлoчки” цeлeй. Cтaтья дaeт нeoбчoдимыe и дocтaтoчныe ycлoвия для cпocoбнocти дocтижeния pядa цeлeй в cлyчae кoгдa cocтoяниe мoжeт быть тoчнo измepeнo, в тo вpeмя кaк дocтaтoчныe ycлoвия для этoй cпocoбнocти дocтижeния дaютcя кoгдa имeютcя нaлицo лишь вычoдныe измepeния иcкaжeнныe пoмeчaми. Cтaтья дaeт aлгopитм для эффeктивнoгo пocтpoeния эллиптичecкич пpиближeний к paccмaтpивaeмым pядaм и пoкaзывaeт чтo этoт aлгopитм пpивoдит к линeйным зaкoнaм yпpaвлeния. Cтaтья тaкжe oбcyждaeт пpимeнeния cвoич peзyльтaтoв к игpaм пpecлeдoвaния и пoбeгa.