Dynamic optimization in the coordination and control of autonomous underwater vehicles

Dynamic optimization in the coordination and control of autonomous underwater vehicles Jo˜ao Borges de Sousa, Anibal Matos and Fernando Lobo Pereira 1 Departamento de Engenharia Electrot´ecnica e de Computadores Faculdade de Engenharia da Universidade do Porto Rua Dr. Roberto Frias, 4200-465, Porto, Portugal {jtasso,anibal,flp }@fe.up.pt Abstract The role of dynamic optimization techniques for the coordination and control of Autonomous Underwater Vehicles (AUV) is discussed. We start with a specification and modeling framework which supports the expression of fundamental coordinated control requirements (e.g., styles of interactions, joint set state constraints induced by sensing and services) as well as the intrinsic synthesis mechanisms. Then, dynamic optimization and non-smooth analysis results are used to show that some essential coordination problems can be can be expressed in terms of invariance w.r.t. to sets, of monotonicity of the trajectories of a dynamic system wrt to some field, or as switchings among value functions. Value functions play a major role in those interpretations, as the reachable set of a dynamical system can be expressed in terms of a level set of a certain value function. The pervasive proximal aiming technique is discussed in this control framework. Keywords: Autonomous Underwater Vehicles, Optimization, Coordination, Non-smooth Analysis. 1 Introduction The last decade has witnessed unprecedented interactions between technological developments in computing, communications, and control, on the one hand, and the design and implementation of networked multivehicle systems with varied degrees of autonomy, on the other. These technological advancements allow us to envision the design of systems which could have not been imagined before. Consider new concepts for the networked operation of underwater vehicles, such as group behavior, cooperative navigation and data collection and mine-hunting, to name just a few. We are interested in the problem of specification and design of motion coordination and control systems for those systems. This problem poses 1Research supported by Funda¸c˜ao da Ciˆencia e Tecnologia project Cordyal and by Funda¸c˜ao das Universidades Portuguesas project COOP. new challenges to control engineering. These challenges entail a shift in the focus of control theory - from prescribing and commanding the behavior of isolated systems to prescribing and commanding the behavior of interacting systems. First, we require vehicles, devices, and controllers with evolving access capabilities to dynamically interact with each other - by exchanging messages and data - in order to execute tasks. Second, we need different notions of what should be observed under different circumstances, giving rise to questions of when two different systems exhibit the same behavior. Third, we need motion coordination models that are highly application dependent, and that may change with time for the same application. Forth, we need to incorporate in analysis and control synthesis the aspects of communication and concurrency that are at the heart of these systems. In this paper we discuss the problem of coordination and control of AUVs in the framework of dynamic optimization. The paper is organized as follows. In Section 2, we discuss some of the challenges posed by new concepts for the operation of multiple AUVs. We show that some of the fundamental aspects of coordination namely set-based joint state constraints and objectives, styles of interactions, and information structures are best phrased in the framework of dynamic optimization. In Section 3 we introduce notation and definitions. In Section 4, we survey and use results from dynamic optimization and non-smooth analysis to show that, at least conceptually, some of the fundamental aspects of coordination can be phrased in terms of invariance wrt to sets, of monotonicity of the trajectories of a dynamic system wrt to some scalar field, as switchings among value functions, or as degenerate optimal control problems. In Section 5 we draw some conclusions and discuss future research. 2 Coordination and control of networked multi-vehicle systems 2.1 Introduction We have been involved in the specification and design of a particular type of distributed systems – networked multi-vehicle systems – and we are interested in p. 1 For example: the Automated Highway System [22, 21, 23], Mobile Offshore Base [9, 8], Autonomous Underwater Vehicles [10], Unmanned Combat Air Vehicles and Air Traffic Management [20]. There are several aspects to this problem. Specification.. How to express user requirements, and how to map them onto technical requirements? Design. How construct a system-level capability by appropriately organizing agents that execute a small set of tasks? Verification. How to check if the design indeed satisfies the specification? How to compare alternative designs? In this paper we are interested in the problem of design. 2.2 Patterns of coordination and control In order to understand patterns of coordination and control we need to understand why we require vehicles to coordinate not only their motions, but also the utilization of their resources. Vehicles, sensors, and other entities are combined to provide services at certain locations, at certain times. In fact, at a certain level of abstraction we are not interested in specific vehicles but in the services that have to be delivered at those locations and times. In the end, service delivery results from the actions of vehicles. For example: 1) to cover a certain area with sensors, 2) to search and destroy targets, 3) to find the minimum of a certain environmental quantity (e.g. the temperature of the ocean in a certain area). A simple and subtle feature of the coordination and control of automated vehicles - that distinguishes this problem from the general coordination problem - is that services are delivered in the same space where the same vehicles and other entities evolve. This means that specification and design involve manipulations of entities in this space, namely sets and points. In fact, some services can be completely specified by the evolution of a set in space, whereas some technological constraints, such as communication constraints, can be expressed as set inclusion problems. In summary, at the root of coordination and control problems for automated vehicles are set-based joint state constraints and objectives. Another important feature of the coordination and control of automated and/or driver-assisted vehicles is related to the nature of the constraints and interactions. Consider a group of heterogeneous vehicles with evolving access capabilities. In order to deliver a service that cannot be physically realized with a single vehicle, we require those vehicles to interact by exchanging messages and data while satisfying joint state-constraints. But this apparent physical limitation can be used to our advantage. By considering vehicles, sensors, and other devices as basic entities that can be manipulated and linked in varied forms to achieve different goals, we are able to specify the behavior of the ensemble in a style that resembles that of a programming language. Imagine we want to compute the minimum of temperature in a given region of the ocean with a group of AUVs with limited communication capabilities. We can implement an iterative optimization algorithm to find the minima of the temperature scalar field with the additional dynamic and technological constraints: vehicles exchange the data collected in order to determine the next waypoints where they will exchange data again. In practice, vehicles have communication ”rendez-vous” at those waypoints. Pursuing this idea further we can envisage communication ”rendez-vous” - ”spatial rendez-vous” in regions where communication is allowed - for vehicles where these vehicles exchange data and mission specifications. This may be of interest in covert operations where we have vehicles acting as ”go-betweens” for coordination and control. Obviously the problem of mobility is also of interest: Vehicle A is under the dependence of some controller that may change with time as the vehicle evolves in time-space. We are interested in controlling and manipulating these dependencies. The problem of design consists in utilizing a given set of assets to satisfy the specification. This can be done in several different ways depending on the available assets. On the other hand, a set of assets comes with utilization rules that reflect technological constraints and define the ways we can combine and recombine those. For our purposes we are interested in those rules that affect motion control and coordination, i.e., those rules specified as joint-state constraints for specific combinations of assets, and also as linking rules. In practical terms when it comes to design we add additional constraints and objectives to the ones defined in the specification. For the purpose of specification we are interested in what happens in the 3-dimensional space. For design we have to consider other spaces, namely the spaces of relative motions, and mappings between these spaces and the reference space. Most of the features of motion coordination and control of multiple vehicles, in particular AUVs, can be phrased in terms of one of the following classes of problems. Coordinated invariance. Set-based joint state constraints arise in spaces of relative distances and/or velocities and, in some cases, are described by ellipsoidal or polyhedric constraints. Formally, this means that we want to find the sets of states, and of controls that maintain the overall system invariant wrt to the constraints. The violation of the constraints may have several meanings according to the specific example: communication drop-outs, etc. Note that these constraints concern only relative motions. This means that the p. 2 ensemble is available for motions that do not violate those constraints. Coordinated reachability with invariance constraints. Coordinated descent with invariance constraints. Switching costs. 3 Definitions Proximal normals are direction vectors pointing outward from a set, generated by projecting a point to the set. Proximal subgradients have a certain local support property to the epigraph of a function. Namely, the proximal gradient of a lower semicontinuous function f at x∈dom f is, within an appropriate scaling factor, a component of the proximal normal to the epigraph of the function at the point (x, f(x)). Definition 1 (Proximal subgradient) Consider θ: <n→(−∞,∞]∈F. A vector ξ∈ <nis a proximal subgradient of θat x provided (ξ, −1) ∈NP epiθ(x, θ(x)). Note that epi θis a closed subset of <n+1. Definition 2 (Proximal subdifferential) The set (that can be empty) of all proximal subgradients of θ(.)at x is denoted by ∂Pθ(x). If x /∈domθ, then ∂Pθ(x) = ∅by definition. Next we provide an operational definition of the proximal sub-gradient: Theorem 1 [Proximal subgradient inequality] Let f ∈F. Then ξ∈∂Pf(x)⇐⇒ ∃σ, η :f(y)≥f(x)+hξ, y−xi−σky−xk2,∀y∈B(x;η) (1) Remark 1 (Geometric interpretation) The proximal subgradient inequality asserts the existence of a parabola p(y) = f(x) + hξ, y −xi − σky−xk2,∀y∈ B(x;η)which “locally fits” under epi f at (x, f(x)). Consider again the multifunction F and the associated differential inclusion: F: ˙x(t)∈F(x(t)) Definition 3 (Lower hamiltonian h) h:<×<n× <n→ <, h(t, x, p) = min v∈F(t,x)hp, vi(2) Definition 4 (Upper hamiltonian H) H:<×<n× <n→ <, H(t, x, p) = max v∈F(t,x)hp, vi(3) Proposition 1 Under the Standing Hypotheses on F the lower hamiltonian h satisfies the following properties: 1. h is lower semi-continuous in (x,p) and concave and continuous in p. 2. h is supperadditive in p: h(t, x, p+q)≥h(t, x, p)+ h(t, x, q); h(t, x, 0) = 0 3. v∈F(t, x)⇐⇒ h(t, x, p)≤ hp, vi,∀p∈ <n; 4. v∈F(t, x) + rB(r≥0) ⇐⇒ h(t, x, p)≤rkpk +hp, vi,∀p∈ <n 4 Results from dynamic optimization [12] status of research on distributed systems [24]. [11] [14] [13] [15] [16] [1] [4] [5] [7] [18] [6] [3] [2] [19] [17] 4.1 Coordinated invariance Definition 5 (Proximal aiming condition) Pick s∈projS(x(t)). If hf(t, x(t)), x −si ≤ 0 (4) then the state will move towards the set S. The geometric interpretation is quite simple. For each t, the velocity vector f(t,x(t)) has a component pointing in a direction opposite to the direction of the normal to the set at the projection projS(x(t)). Remark 2 The following proposition provides a formal characterization of this intuition in terms of the decrease of the distance function to the set S. Proposition 2 Let: 1. f satisfy the linear growth condition: kf(t, x)k≤ γkxk+c, ∀(t, x) 2. x(.) be an Euler arc for f on [a,b]. 3. ∀t, x(t)∈Ω, where Ωis an open set. p. 3 Suppose that every (t, z)∈[a, b]×Ωsatisfies the proximal aiming condition, hf(t, z), z −si ≤ 0, with s= projS(z). Then we have: dS(x(t)) ≤dS(x(a)),∀t∈[a, b] Definition 6 We denote x(a,b) the arc x from x(a) to x(b). Definition 7 (Weakly invariant (WI)) The system (S, F) is weakly invariant (WI) if: ∀x0,∃x(0,∞) : x(0) = x0, x(t)∈S, ∀t≥0 Remark 3 This property is also called viability. Theorem 2 ∀x∈S, h(x, NP S(x)) ≤0⇒(S, F)is WI (5) Problem 1 Under which conditions can the trajectory of a differential inclusion be steered to some compact set S in finite time given an initial condition outside the set. In this section we will address local results. Later we will discuss attainability in the context of minimal-time functions, dynamic programming and Hamilton-Jacobi equations. Definition 8 (Locally weakly attainable) The system (S, F) is locally weakly attainable of radius r if: ∃r > 0,∃T > 0 : ∀α:dS(α)< r ⇒ ∃(x:x(0) = α)∧(x(t)∈S, ∀t≥T) (6) If, in addition, ∃c > 0 : dS(x(t)) ≤dS(x(s)) −c(t−s),∀0≤s≤t≤T Then c is called the rate of attainability of (S,F). Definition 9 (Locally strongly attainable) The system (S, F) is locally strongly attainable of the corresponding radius and rate if the properties of definition 8 hold for every trajectory of F, eventually for different T. 4.2 Invariance with respect to a scalar field 4.3 Controls with switching costs 4.4 Degeneracy and aggregation 5 Conclusions The coordination and control of networked vehicle systems poses significant challenges to control, computation, and networking and new developments are being triggered by the interactions between engineering practice and its theoretical background. In this paper, we drawn the reader’s attention to the fact that dynamic optimization provides a rich pool of results for the analysis and synthesis of coordinated control strategies. Moreover, in the framework of dynamic optimization we are able to translate high level specification onto workable problems without introducing additional and unnecessary constraints arising when we consider other design techniques. The price for this less restrictive setting is added complexity for the design. Acknowledgments The authors also thank Professors Pravin Varaiya and Alexander Kurzhanski for stimulating discussions and valuable comments, insights and contributions. References [1] Jean-Pierre Aubin. Viability theory. Birkhauser, 1991. [2] Martino Bardi and I. Capuzzo-Dolcetta. Optimal control and viscosity solutions of Hamilton-JacobiBellman equations. Birkhauser, 1997. [3] I. Capuzzo-Dolcetta and L. C. Evans. Optimal switching for ordinary differential equations. SIAM J. Control and Opt., 22(1):143–161, 1984. [4] F. H. Clarke. Optimization and Nonsmooth Analysis. SIAM, 1990. [5] F. H. Clarke. A proximal characterization of the reachable set. Systems & Control Letters, 27(3):195–7, 1996. [6] F. H. Clarke, Y.S. Ledyaev, and A.I. Subbotin. The synthesis of universal feedback pursuit strategies in differential games. SIAM Journal on Control and Optimization, vol.35(no.2):552–61, 1997. [7] F. H. Clarke and P. R. Wolenski. Control of systems to sets and their interiors. Journal of Optimization Theory and Applications, 88(1):3–23, 1996. [8] J. Borges de Sousa, A. Girard, and K. Hedrick. Real-time hybrid control of mobile offshore base scaled models. In Proceedings of the American Control Conference, 2000. [9] J. Borges de Sousa, A. Girard, and N. Kourjanskaia. The mob shift simulation framework. In Proceedings of Third International Workshop on Very Large Floating Structures, pages 474–482, 1999. [10] J. Borges de Sousa and F. Lobo Pereira. A generalized vehicle-based control architecture for multiple p. 4 auvs. In Proceedings of the OCEANS ’95 MTS/IEEE, pages 1643–50. IEEE, 1995. [11] F. H. Clarke et. al. Nonsmooth Analysis and Control Theory. Springer, 1998. [12] IEEE, editor. IEEE standard for application and management of the systems engineering process. IEEE, 1999. [13] A. N. Krasovskii. Control under lack of information. Birkhauser, 1995. [14] N.N. Krasovskii and A.I. Subbotin. Gametheoretical control problems. Springer-Verlag, 1988. [15] A. B. Kurzhanskii. Advances in nonlinear dynamics and control : a report from Russia. Birkhauser, 1993. [16] A. B. Kurzhanskii. Ellipsoidal calculus for estimation and control. Birkhauser, 1997. [17] Robin Milner. Communicating and mobile systems : the Π-calculus. Cambridge University Press, 1999. [18] E.D. Sontag and Y.S. Ledyaev. A lyapunov characterization of robust stabilization. Journal of Nonlinear Analysis, 37:813–840, 1999. [19] D. Swaroop and J. K. Hedrick. String stability of interconnected systems. IEEE Transactions on Automatic Control, 41(3):349–57, 1996. [20] C. Tomlin, G. Pappas, and Shankar Sastry. Conflict resolution for air traffic management: A study in multi-agent hybrid systems. IEEE Transactions on Automatic Control, 43(4):509–521, 1998. [21] P. Varaiya. Smart cars on smart roads: problems of control. IEEE Transactions on Automatic Control, 38(3):195–207, February 1993. [22] P. Varaiya. Towards a layered view of control. In Proceedings of the 36th IEEE Conference on Decision and Control, pages 1187–90. IEEE, 1997. [23] P. Varaiya and S. E. Shladover. Sketch of an ivhs systems architecture. In Proceedings of the VNIS ’91. Vehicle Navigation and Information Systems Conference, pages 909–922. IEEE, 1991. [24] P. Varaiya, T. Simsek, and J. Borges de Sousa. Communication and control in hybrid systems. In accepted as a tutorial session for ACC 2001, 2001. p. 5