Coordinated control strategies for networked vehicles: an application to autonomous underwater vehicles

Coordinated control strategies for networked vehicles: an application to Autonomous Underwater Vehicles Jo˜ao Borges de Sousa and Fernando Lobo Pereira Departamento de Engenharia Electrot´ecnica e de Computadores Faculdade de Engenharia da Universidade do Porto Rua Dr. Roberto Frias 4200-465, Porto Portugal {jtasso, flp}@fe.up.pt Abstract The specification and design of coordinated control strategies for networked vehicles and systems is discussed. A strategy to find the local minimum of an oceanographic scalar field with networked autonomous underwater vehicles (AUV) is presented. The strategy consists in coordinating the motions of the AUVs to implement a modified version of the simplex optimization algorithm. In the original algorithm, the scalar field is given by a function. In the modified version, the scalar field is given by the phenomenon itself. The AUVs sample the phenomenon to calculate the directions of descent, and to minimize the phenomenon along each direction of descent. The strategy is discussed in the more general context of coordination and control of networked vehicles and systems. 1 Introduction Today, and partly due to our involvement in the design and implementation of networked vehicles and systems, we have a better understanding of the issues arising in the coordination and control of these systems [9]. In order to encompass all of these issues we need to consider potential applications from diverse fields, each presenting its own unique challenges to our efforts to generalize and formalize. Recognizing that we are still taking the first steps in this direction, we have been actively involved with the potential users of networked vehicles and systems. This enables us to envision concepts for the operation of systems which could not have been imagined before. In this paper, we present some concepts for the operation of autonomous underwater vehicles, and formulate the corresponding coordination and control problems in the setting of dynamic optimization. In this setting, we express complex requirements, such as the disjunction of joint-state constraints and relative motion coordination, in terms of invariance and of level sets of value functions. We focus on mapping set-valued requirements, expressed within the language of set theory and logic, onto problem formulations where these requirements are expressed in terms of set-valued operations. 1 The paper is organized as follows. In section 2, we discuss a preview of a mission involving autonomous underwater vehicles to provide a concrete referent for our overview. In section 3, we discuss the patterns of coordination and control arising in this mission and show that they are quite general, and not specific to this application. In section 4, we motivate and illustrate our specification and design approach by reference to this mission. In section 5, we draw some conclusions and discuss future work. 2 Preview of an oceanographic mission Let us start with a preview of an oceanographic mission conceivable in a near future. Imagine two teams of Autonomous Underwater Vehicles (AUVs) that must coordinate their motions to find the local minimum of some oceanographic phenomenon. •The first team, denoted as LPS, provides a Local Positioning System (LPS) service to other team. This system can be viewed as an underwater version of the Global Positioning Service (GPS). •The second team, denoted as S, uses the LPS service for localization and provides a search service. The Local Positioning System works as follows. Each LPS vehicle has a GPS receiver and an acoustic transponder – the vehicle is required to operate at the surface to receive the GPS signal. The transponder emits regularly, with a known frequency, an acoustic ping encoding the time t when it was emitted, and the name and location of the emitter at time t. The time t and the position of the emitter are given by the GPS receiver. The AUVs from the S team are equipped with an acoustic system. This system detects the acoustic pings, and decodes them to extract the position and name of the emitter, and the time when the acoustic ping was emitted. This information together with the time of arrival of the ping is used to calculate the distance between the AUV and the emitter. To calculate its absolute position the AUV needs to receive pings from at least three sources – vehicles from LPS. In order to minimize the calculation error we require these three sources to be the vertices of a triangle. Due to attenuation, the LP S service is only available within a neighborhood P(t) of the LPS team. The search service works as follows. The Steam implements a modified version of the simplex optimization algorithm to find the local minimum of the phenomenon. Each vehicle has a suite of oceanographic sensors – to sample the phenomenon – and a low-bandwidth underwater acoustic communication system – to implement the search strategy in coordination with the rest of the team and with the LP S team. In terms of motion coordination the Steam assumes the role of the leader. The LP S team controls the motions of its vehicles in order to keep all the elements of the Steam inside P(t). It does this based on the information exchanged with the Svehicles. 2 Hereafter we designate this mission preview as the oceanographic mission, or simply the mission. 3 Coordinated control of vehicles and systems 3.1 Why motion coordination? From the analysis of the oceanographic mission we may infer some of the reasons why we need to coordinate the motions of heterogeneous vehicles: Functional complementarity. It is generally the case that space is at premium in autonomous vehicles, whether for sea, air, or land applications. Moreover, sensing and sampling strategies may require the spatial distribution not only of sensors, but also of different components of the same sensing system. In both cases we need to distribute capabilities – multiple sensors or different components of the same sensor – among different vehicles. Spatial-temporal distribution of services. Some services, for example communication services, have to be distributed among multiple vehicles to cover a given area. Sensing and acting on the world. Sensing involves establishing spatial relations between the vehicle where the sensor is mounted, and the object or phenomena being sensed. The same happens with vehicles with the capability to act upon the world. One such example arises with Unmanned Combat Air Vehicles (UCAV), that are capable of launching attacks with missiles. For the attack to be effective, we require the UCAV to satisfy a predicate on the distance and azimuth from the target before a missile is launched. Algorithmic motion specifications. At a certain level of abstraction, vehicles are points in the 3D space. The motion requirements for several applications, for example in the oceanographic mission, are expressed as an algorithm, that may, or may not, be implementable with the motions of those points. 3.2 Patterns of coordination and control We design teams to provide services that cannot be provided by a single vehicle. This means that vehicles within a team, and teams within interacting teams, have to coordinate their actions – motions and the utilization of their capabilities – to provide those services. This is done according to patterns of coordination and control. For example, the vehicles in our oceanographic mission exhibit patterns of coordination and control that are quite general, as we will see. Satisfaction of joint state and capability constraints. A service requires the satisfaction of predicates on the capabilities and on the relative motions of the vehicles providing the service. Team as a specific entity. A team comes into existence through the coordinated actions of 3 its vehicles. This means that, with respect to the other teams, each team acts as a single unit, thus engaging, as a single unit, in interactions with those teams. For example, the LPS follows the S team in order to keep S inside P(t). Coordination of teams. Services may build on other services. In fact, we may need to recruit the utilization of several teams to deliver a service. This requires the nesting of services, of constraints, and of controllers. For example, the LPS and the S team jointly provide a search service. Note that the modes of coordination at this level are richer than the modes of coordination at the intra-team level. First, teams form spatial entities whose shape and evolution we may want to control. Second, it may be possible, and desirable, to transfer assets among teams. Interactions with externalities. Teams are designed to interact with the world, and to intervene in the world through sensing and actuation. This means that we close some of the control loops with the external environment. This relates to the next issue. Algorithmic based activities. Teams have to interact with other teams, or with the world. In the absence of models of the world that are based on the principles of physics, we have to write specifications, and their implementations, as algorithms. For example, the S team is seeking to find the local minima of an oceanographic phenomenon. Mobility of links. In order to coordinate their activities, the vehicles within a team (e.g. the S team), and groups of teams (e.g. the S and LPS teams), interact among themselves, and with other entities. To do this, they establish and destroy links among them. This means that they form a system with an evolving structure. The structure evolves when links change. Hence, establishing or destroying a link is a control action that may result in a different behavior for the structure. We can find the same patterns of interactions in other problem domains, for example in applications involving Unmanned Air Vehicles (UAV)s or Unmanned Combat Air Vehicles (UCAV) (see [8] for an extensive survey on applications of these vehicles). UAVs and UCAVs are in high demand for military, scientific and civilian applications. Military operations present the most challenging scenarios. For military operations UAVs are tasked to “dirty”,“dull”, and “dangerous” operations. “Dirty” refers to reconnoitering areas that may be contaminated, “dull” applies to surveillance, zone interdiction or sentry duty, while “dangerous” is related to obvious threats, such as those posed by the suppression of enemy air defenses (SEAD). In SEAD missions we have spatial and temporal rendezvous where vehicles form teams. In zone interdiction missions we have teams of UCAVs that coordinate their motions to maximize the rate of coverage. In reconnaissance and target finding missions we have search-based algorithms with integration of data from different sensors mounted on different vehicles. Moreover, with Unmanned Combat Air Vehicles, we may want to emulate the behavior of fighter pilots, where all types of engagements are guided by algorithmic procedures, or tactics. Tactics, also called plays, are used in robotic games 4 involving antagonistic teams of robots. The collection of all tactics, or plays, is called the play-book. 4 Illustration of the approach In this section we motivate and illustrate our specification and design approach by reference to the oceanographic mission. 4.1 Introduction The potentially rich behavior of networked vehicles and systems results from the way agents – vehicles, controllers, service providers, and devices – are connected, and also from the way connections among these agents evolve with time, i.e. from the control architecture. This is why we turn our attention to architectural and specification issues1. Our approach addresses the issue of formal specification, and treats the design problem as a refinement of the specification. Consider the mission description from section 2. First, it is not formal, i.e., it lacks a vocabulary of relevant concepts and rules that determine how they can be used. Second, it is not complete, i.e., it does not contain all components, connections, etc., intended to be true at all levels of detail. Or, equivalently, from it we cannot assert which properties will hold in the implementation, and which properties should not be present in the implementation. Third, we cannot reason about the description, or prove facts about it. We address these issues in the following way: •We represent specifications as logical theories. We introduce a vocabulary of the relevant components and well formedness axioms that determine how they can be used. We use set-theoretic constructs that are amenable to mathematical manipulation at the design stage. •We write open specifications for components. These specify the component itself, and not the complete system containing it. 1The architectures of large systems are often described by a hierarchy of related architectures. A hierarchy of architectures is a linear sequence of individual architectures that may differ with respect to the number of components and connections among them. The current level of informality is one of the problems with architectural design. For example, quite often there are no formal mappings between adjacent architectures in the hierarchy. Hence, it is not possible to assert that one architecture is an implementation of a more abstract one. To be able to answer this question we need to define equivalent behaviors, and we need to study under which conditions are behaviors preserved under those mappings. This means that we need more than syntactic checks; we need to check for the semantic properties of an architecture. This problem has been addressed by the computer science community under the designation of “architecture refinement” (see for example, [14]). 5 •We define invariants, that we require the implementation to satisfy. The invariant captures the essence of what makes an implementation correct. In practice the invariants define the set of behaviors that satisfy the predicates associated with the specified requirements. We formulate the coordination and control problems in the setting of dynamic optimization. In this setting we express complex requirements, such as the disjunction of joint-state constraints and relative motion coordination, in terms of invariance, of level sets of value functions, and of reachability. We focus on mapping the specification, expressed within the language of set theory and logic, onto problem formulations where these specifications are expressed in terms of set-valued operations. In doing this, we are able to derive conditions under which the invariants will be true, and synthesize controllers that ensure invariance. Basically, the design is a refinement of the specification. 4.2 Specification In this section we introduce the main concepts and sketch the specification for our mission. 4.2.1 Main concepts We use simple concepts for specification: components and connectors. A component has an internal structure, and a port. A connector has two or more ports, and specifies how to components can be linked together. We can build components from other components, using connectors. This allows for hierarchical organization. A particular arrangement of components and connectors is termed a configuration. We impose rules on the way components are connected. This defines a configuration style – a vocabulary of design elements, well formedness constraints that determine how they can be used, and a semantic definition of components associated with the style. The interface of a component defines available services and conditions under which the service is provided. We connect components with connectors defining relations among the interfaces of those components. Components, interfaces, and connectors are treated as first-class objects – i.e., they have a name and they are refinable. Abstract architectural objects can be decomposed, aggregated, or eliminated on a concrete architecture. The semantics of components is not considered part of an architecture, but the semantics of connectors is. 4.2.2 Intra and inter-team specification Algorithm. The Steam implements a modified version of the simplex algorithm that is described next. We could have used another algorithm. This one suffices to illustrate our approach in spite of its simplicity. Consider, for the sake of simplicity, a scalar field f(x) : <2→ < evolving in the horizontal plane with a unique local minimum in the region of interest. We are interested in finding 6 this minimum. At the beginning of each iteration i, we have three points Ai, Bi, Ci, and three values of the scalar field f(Ai), f(Bi), f(Ci), where we have labelled the points so that f(Ai)≤f(Bi)≤ f(Ci). The sequence of computations is described next. Algorithm 1 (Modified simplex). Set i:= 1. Consider three points A1, B1, C1forming a triangle. Repeat until finding minimum. 1. Take the segment joining Aiand Bi. Define the midpoint of this segment as zi. Define the cone K(zi)with apex at ziof all the unit vectors from Cito zi+δ×B, where δis a parameter and B the unit ball. 2. Define the set of feasible directions at zias K(zi). 3. Select one vector vfrom K(zi). 4. If, at zi, and for any direction wsuch that hw, vi ≥ 0, the directional derivative of falong wis non-negative, i.e., f0(zi;w)≥0, then stop. In this situation, the point of minimum is located within the triangle with vertices Ai,Bi, and Ci. If not then, starting at zi, find the minimum of f in the direction of v. Denote the point where the minimum is attained as Ai+1. Then f(Ai+1)≤f(Ai)≤f(Bi)≤f(Ci). 5. Rename Aiand Bias Bi+1 and Ci+1. 6. Set i:= i+ 1. This algorithm is scalable with respect to the number of vehicles used to implement it. With one vehicle, the ideal implementation would require this vehicle to jump from point Ai+1 to point zi+1 at the beginning at each new iteration. With two vehicles, the ideal implementation would require one of them to be at position zi+1 when the other reaches the point Ai+1. Available assets. Consider the following assets. 1. A set SV, of nSV identical surface vehicles with a GPS receiver, a transponder, a radio, and an acoustic modem. The ranges of the radio, transponders, and acoustic modems are respectively rr,rtand ra. 2. A set AUVu, of nuidentical AUVs with a Conductivity Temperature Depth (CTD) sensor, an acoustic modem, and a navigation acoustic system. The range of the acoustic modem is ra. 3. A set AUVs, of nsidentical AUVs mounting the same devices as the surface vehicles, plus the sensor pack mounted on all the vehicles from AUVu. These multi-role vehicles may be assigned to the LPS, or to the S teams. 7 We use the surface vehicles to implement the LP S team, and the AUVs to implement the LPS, and Steams. The LPS team is composed of two sets of vehicles, LPSSV and LPSAUV , where LPSSV =SV, and LPSAUV ⊆ AUVs. The S team is also composed of two sets of vehicles, Suand Sv, where Su=AUVu, and Sv⊆ AUVs. We label each vehicle in S(LPS) with a number i(j), where i(j) ranges from 1 to nS(t) (nLP S(t))), and nS(t),(nLP S (t)) varies with time. We denote the (x,y,z) position of the i−th(j−th) vehicle from S(LPS) by XSi(t),(XLP Si(t)). Distance function. In what follows we express the Euclidean distance between two points X, Y in <3as d(X, Y ). First, we specify the behavior for each team, and then the required inter-team behavior. LPS team. The LPS team provides a positioning service to other vehicles. At time t, the service is available at all locations Xsuch that there are at least three vehicles from LP S within distance rt– the range of the transponder – from X. The set of all such points is denoted P(t). P(t) = {X∈ <3:∃i, j, k (k6=i)∧(i6=j)∧(j6=k)∧(d(XLP Sj, X)≤rt)∧ (d(XLP Si, X)≤rt)∧(d(XLP Sk, X)≤rt)}(4.1) The vehicles in LPS must satisfy the following motion constraints2. Service constraints. At least three vehicles from LPS are required to form a triangle. We express a relaxed version of this requirement using the distance function das follows: ∃i, j, k ∈LPS : (j6=i)∧(i6=k)∧(k6=j)∧(d1≤d(XLP Si, XLP Sj)≤d2)∧ (d1≤d(XLP Si, XLP Sk)≤d2∧(d1≤d(XLP Sk, XLP Sj)≤d2) (4.2) Structural constraints. The LPS vehicles have to coordinate their motions to satisfy the service constraints, and to follow the S team. This is why we require the LPS vehicles to form a communication network where every two distinct vehicles should be able to communicate between them. We express the requirement as graph connectedness. To express graph 2There are two distinct types of constraints. The ones required for the team to coordinate its operations and to maintain its integrity, let us call them the structural constraints, and the ones required for the team to provide services, let us call them the service constraints. The structural constraints have precedence over the service constraints. The violation of the former implies the collapse of the team, while the violation of the latter degrades the way the service is delivered. From the above we conclude that we are in the presence of two levels of dynamic behavior. The first one ensures that the structural constraints are an invariant set for the operation of the team, the internal dynamics. The second one ensures service delivery, the external dynamics. The two levels of dynamic behavior are obviously coupled. We want to control this coupling so that the team is able to respond to service requests as fast as possible. This property is called flexibility. The specification of both types of constraints should be scalable to accommodate the addition, or deletion, of vehicles to and from the team. 8 connectedness formally we need some terminology and notions from graph theory3. Define the graph T as follows. Each vehicle in LPS is represented by a vertex. There is an edge between two vertices whenever the distance between the corresponding vehicles is less than the radio communication range rr. The communication constraints are expressed as follows: The graph T is connected (4.3) S team. The vehicles from the Steam implement a modified version of the simplex algorithm. The implementation of this algorithm requires permanent communication among the vehicles. Here, again, we need graph connectedness in a graph K defined as follows. To each vertex in V there corresponds a vehicle in S. There is an edge between two vertices whenever the distance between the corresponding vehicles is less than ra. The constraint is expressed as: The graph K is connected (4.4) LPS-S coordination. There are two coordination requirements: 1. The vehicles from the S team should remain inside the set P(t): ∀i∈S:XSi(t)∈P(t) (4.5) 2. The vehicles in both teams should be able to communicate among themselves. If rais the maximum range of communication we express this constraint as follows: ∀t, ∀i∈S, ∀j∈LPS :min d(XLP Sj(t)), XSi(t)) ≤ra(4.6) Task. Control the motions and services of the two teams to find the minimum of the temperature f in a given zone of the ocean in minimal time, and using the simplex algorithm. 4.2.3 Remarks Now, rather informally, let us consider this specification in the light of the concepts introduced before, i.e., components and connectors. Consider the Steam. We specify this team as a component. The interface of the team includes, as outputs, the search service, the set CS(t) – the convex closure of the locations of the members of the team) – and the set DS(t) – the set of locations where other vehicles can communicate with this team – and, as inputs, a localization service for the whole team. The LPS team is treated analogously. The interface includes, as outputs, the positioning 3A graph G is a finite nonempty set V together with an irreflexive symmetric relation R on V. V is the vertex set. We denote by E the set of symmetric pairs in R. Each element in E is called and edge, and the set E is called the edge set of G. A u-v walk in G is an alternating sequence of vertices and edges of G, beginning with u and ending with v, such that every edge joins the vertices immediately preceding it and following it. Two vertices u and v in a graph G are connected if u=v, or if u6=vand a u-v path exists in G. A graph is connected if every two vertices of G are connected. 9