Beard

Coordination Variables and Consensus for Multiple Vehicle Systems: 

Coordination Variables and Consensus for Multiple Vehicle Systems Randy Beard Tim McLain Brigham Young University

Outline: 

Outline Overview of cooperative control literature. Need to move beyond formation control. Challenges inherent in cooperation. Coordination variables as a method to articulate (centralized) team strategies. Decentralized algorithms require consensus building techniques. Examples: Cooperative timing Formation control.

Literature on Cooperative Control: 

Literature on Cooperative Control Formation Control Mobile robots (Wang 91, Balch & Arkin 98, Lewis & Tan 97, Sugar & Kumar 98, Fax & Murray 02, Eren & Belhumeur & Morse 02, Ogren & Egerstedt & Hu 02, Belta & Kumar 02, Hong, Shin, & Ahn 01, Monteiro & Bicho 02, Yamaguchi 97, Yamaguchi & Burdick 98, Desai, Ostrowski & Kumar 98, Gentili & Martinelli 00, Hashimoto 95, Parker 98, Pledgie, Hao, Ferreira, Agrawal & Murphey 02, Sugihara & Suzuki 96, Tanner, Kumar & Pappas 02) Unmanned air vehicles (Giulietti & Pollini & Innocent 00, Proud, Pachter, & DAzzo99, Anderson & Robbins 98, Blake & Multhopp 98, Chichka & Speyer 98, Blake & Multhopp 98, Fax & Murray 01, Schumacher & Singh 00) Autonomous underwater vehicles (Leonard & Fiorelli 01, Stilwell & Bishop 00) Satellites (Kang & Yeh 02, Carpenter 02, Kapila, Sparks, et. al. 00, Das, Cobb & Stallard 98, Folta, Bordi & Scolese 92, Folta & Quinn 98, Guinn 98, How, Twiggs, Weidow, Hartman & Bauer 98, McInnes 95, Sedwick, Kong & Miller 98) Spacecraft (Wang & Hadaegh 96, Hadaegh & Lu & Wang 98, Robertson & Inalhan & How 99, Mesbahi & Hadaegh 00, Wie & Weiss & Arapostathis 89, Lau 96, Joshi 98, Lawton, Beard, & Hadaegh 01, Mesbahi 02, Ulybyshev 98) Automated Highways (Sheikholeslam & Desoer 92)

Literature on Cooperative Control (cont.): 

Literature on Cooperative Control (cont.) Non-formation Control Task Assignment (Brandt, Brauer, & Weiss 00, Fontan & Mataric 98,) Cooperative transport (Chen & Luh 94, Hashimoto 95, Miyata & Ota, 00) Cooperative Role Assignment (Emery, Sikorski, & Balch 02) Air Traffic Control (Inalhan, Stipanovic, &Tomlin 02, Sastry, Meyer, Tomlin, Lygeros, Godbole, Pappas 95) Cooperative Timing (McLain, Chandler, Rasmussen, & Pachter 01, Richards, Bellingham, Tillerson, & How 02) Cooperative Search (Rekleitis, Dudek, & Milios 00, Sweeney, Brunette, Yang, Grupen & 02, Wagner, Lindenbaum, & Bruckstein 99)

Major focus on formation control : 

Major focus on formation control Why? Formation control problem reduces to single agent control problems: Single agent high level decision making and path planning for leader. Remaining vehicles are controlled using single agent tracking strategies. Performance metrics are clear. Answer: We search where the light is the brightest. It is not because formation problems are the most important/relevant cooperation problems.

Cooperative control problems: 

Cooperative control problems While there are good reasons for formation control, it seems that there are many more interesting coordination problems: Search and rescue, Cooperative manipulation, Task decomposition among heterogeneous vehicles Team assignment in robot soccer/capture-the-flag Cooperative timing of tasks Rendezvous/Join-up Simultaneous target intercept Task sequencing classification/strike/BDA multi-target sequence etc….

Inherent Challenges: 

Inherent Challenges Complexity: Systems of systems. Communication: Limited bandwidth and connectivity. What? When? To whom? Arbitration: Team vs. Individual goals. Computational resources: Will always be limited

Unsolved problem: 

Unsolved problem We need general theory and approaches to cooperative control. Current approaches to formation control can/should guide our thinking.

Fundamental Axiom: 

Fundamental Axiom Shared knowledge is a necessary condition for coordination.

Focus on Three Examples: 

Focus on Three Examples Meet for Dinner Problem Cooperative timing problems. Required knowledge: Rendezvous time Deep space formation flying. Required knowledge: Configuration of virtual structure.

Example 1: Cooperative Timing: 

Example 1: Cooperative Timing Meet for Dinner: Suppose that We all agree to meet for dinner, but do not decide on a time or place. Later, in our rooms, we discover the problem and start calling each other. Everyone has a phone and can call any other person, but must do so one at a time. Also, suppose that some peoples opinion is valued more than others. What algorithm should be followed to ensure that we all come to consensus on a time and a place.

Practical Example: Coordinated Rendezvous : 

Practical Example: Coordinated Rendezvous vehicles must arrive on these vectors Timing: vehicles must arrive within 1 sec of one another uncertainty 1 sigma 25 miles no-fly detection region boundary boundary boundary no-fly no-fly SAM site loiter penalty Wind 25knots X

Initial Route Plan: 

Initial Route Plan vehicles must arrive on these vectors Timing: vehicles must arrive within 1 sec of one another 25 miles no-fly detection region boundary boundary boundary no-fly no-fly SAM site loiter penalty Wind 25knots X

Pop-up Threat Replan: 

Pop-up Threat Replan vehicles must arrive on these vectors 25 miles no-fly detection region boundary boundary boundary no-fly no-fly SAM site loiter penalty Wind 25knots X ETA change -- replan!

Rendezvous Synchronized: 

Rendezvous Synchronized 25 miles no-fly detection region boundary boundary boundary no-fly no-fly SAM site loiter penalty Wind 25knots X

Slide16: 

Importance of Cooperative Timing Capability Key capability for cooperative UAV flight: “the ability to adjust mission timing on the move to compensate for inevitable changes to plans and still make the time-on-target” Brig. Gen. Daniel P. Leaf Operation Allied Force, Kosovo DoD UAV Roadmap 2002

Cooperative Timing: Critical Information: 

Cooperative Timing: Critical Information Each member of the group must have a common “knowledge” of the time-on-target.

Example 2: Formation Control: 

Example 2: Formation Control

Formation Control: Critical Information: 

Formation Control: Critical Information Each member of the group must have a common “knowledge” of the configuration of the virtual structure.

Coordination Variable: 

Coordination Variable situation or environment decisions or influences cooperation objective cooperation constraint Team Individual Agents How effective is the cooperation? Is the team cooperating?

Coordination Variable (cont.): 

Coordination Variable (cont.) cooperation objective cooperation constraint Team Individual Agents individual cost coordination variable coordination function Coordination variable ´ minimum information needed to coordinated decision or influence: Coordination function ´ individual cost vs. 

Cooperative Control Algorithm: 

Cooperative Control Algorithm Choose Implement cooperative action Agent 1 Agent 2 Agent N Step 1 Step 2 Step 3

Example 1: Cooperative Timing: 

#1 #2 #3 Example 1: Cooperative Timing

Searching CFs for Team Optimal CV: 

loose sequence Searching CFs for Team Optimal CV tight sequence

Simultaneous Arrival Results: 

Simultaneous Arrival Results

Tight Sequencing Results: 

Tight Sequencing Results

Loose Sequencing Results: 

Loose Sequencing Results

Range to Target: 

Range to Target

Coordination Functions: 

Coordination Functions

Experimental Platform: 

Experimental Platform System Architecture

Slide31: 

Autopilot Design for Mini-UAVs BYU UAV BYU Autopilot RF Link Laptop PDA / Voice Operator RF Link

UAV – PDA Control: 

UAV – PDA Control

UAV – Voice Control: 

UAV – Voice Control

Example 2: Formation Control: 

Example 2: Formation Control Supervisor Formation control Spacecraft Local Control broadcast Coordination variable ´ formation state: Coordination function ´ combined tracking error

Decentralization: 

Decentralization One approach to decentralization is to implement the centralized coordination scheme on each vehicle. If each vehicle has identical world knowledge, and implements the same coordination algorithm, they will each produce the same coordination variable. However if the world knowledge on each vehicle is different, then vehicles much reach consensus.

Knowledge Consensus: 

Knowledge Consensus Consensus can be formed at either the input of the coordination algorithm, the output, or both. We will focus on the case where the output data (coordination variable) is to be synchronized.

Definitions: 

Definitions

Invariant Set for Data Consensus: 

Invariant Set for Data Consensus

Consensus and Spanning Trees: 

Consensus and Spanning Trees

Consensus Strategy: 

Consensus Strategy

Consensus with Dissimilar Agents: 

Consensus with Dissimilar Agents

Simulation Results: Constant CV: 

Simulation Results: Constant CV Low gain no noise Low gain noise High gain no noise High gain noise

Time-varying Network: 

Time-varying Network

Simulation Results: Formation Control: 

Simulation Results: Formation Control

Average Coordination Variable Error (Ring communication topology): 

Average Coordination Variable Error (Ring communication topology)

Spacecraft Formation Error: 

Spacecraft Formation Error absolute position and attitude error relative position and attitude error

Control Effort for Spacecraft #1, #7: 

Control Effort for Spacecraft #1, #7 Spacecraft # 1 Spacecraft # 7

Summary: 

Summary We need to develop strategies that address the fundamental difficulties inherent in all coordination problems. For example: Cooperation always requires an exchange of information. What information needs to be shared? Coordination variables How should the information be acted upon? Need to be robust to dissimilar information. Need to ensure that team members have sufficiently similar information. Consensus building