Dynamic Optimization for Reachability Problems 1

Dynamic Optimization for Reachability Problems1

A.B.Kurzhanski2and P.Varaiya3

Abstract This paper uses dynamic programming techniques to describe reach sets and related prob-lems of forward and backward reachability.The original problems do not involve optimization cri-teria,and are reformulated in terms of optimization problems solved through the Hamilton-Jacobi-Bellman equations.The reach sets are the level sets of the value function solutions to these equa-tions.Explicit solutions for linear systems with hard bounds are obtained.Approximate solutions are introduced and illustrated for linear systems and for a nonlinear system similar to that of the Lotka-V olterra type.

Key Words.Reachability,target set,Hamiltonian,dynamic programming,Hamilton-Jacobi-Bellman equations,nonlinear systems,convex analysis.

1Introduction

We consider the problem of describing the set of states that are reached with available controls.The notion of reachability has been used to solve“classical”problems in optimal control and differential games(Refs.1-4).Recent activities in advanced automation and navigation have promoted new interest in this problem,(Refs.5-9).The present paper approaches reachability through appropriate problems of dynamic optimization,solved using generalizations of Hamilton-Jacobi techniques. Sections1and2present a problem of optimization that produces,through the solution of some forward Hamilton-Jacobi-Bellman(HJB)equations,value functions whose level sets are precisely the reach sets.Section3describes solvability(or backward reachability)sets consisting of the states from which it is possible to reach a given target set.These sets may be found through a backward HJB equation.However,a direct explicit solution of the HJB equation is rarely possible.An important exception are the equations for linear systems with convex constraints,whose solutions are given in terms of a duality problem of convex analysis.A similar situation arises in systems with Hamiltonians of a special simple type(Sections4,5).

Related problems such as describing the reach sets that avoid a given set or are completely absorbed in a given set,may also be studied through value functions(Section6).The dif?culties in?nding the exact solutions to the HJB equations lead to schemes for approximate estimates of the reach sets.The scheme given here is a comparison principle:the original HJB equation is substituted by an HJB-type inequality of a simpler structure.As indicate
d in Section7,the substitute produces overestimates of the reach sets.

Related problems such as describing the reach sets that avoid a given set or are completely absorbed in a given set,may also be studied through value functions(Section6).The dif?culties in?nding the exact solutions to the HJB equations lead to schemes for approximate estimates of the reach sets.The scheme given here is a comparison principle:the original HJB equation is substituted by an HJB-type inequality of a simpler structure.As indicated in Section7,the substitute produces overestimates of the reach sets.

1This research was supported by the National Science Foundation,Grant ECS9725148.

2Professor,Department of Computational Mathematics and Cybernetics,Moscow State(Lomonosov)University, Moscow,119899,Russia

3Professor,Department of Electrical Engineering and Computer Science,Berkeley,CA94720.

1

Word文檔免費下載：

（共25頁）