|
UPS Foundation Professor, Chair Mechanical Engineering & Applied Mechanics |
Regents' Professor College of Computing Georgia Institute of Technology |
|
James Marshall Wells Professor Mechanical Engineering U. |
Marc Steinberg Office of Naval Research |
|
Research Scientist GRASP lab |
|
There are many technical barriers to the deployment of teams of cooperating, heterogeneous UAVs. The assignment of multiple tasks to multiple heterogeneous assets is an unsolved problem and is further complicated by the presence of differential constraints in dynamically-changing environments. The command and control of individual UAVs require real-time solutions to motion planning problems with spatio-temporal differential constraints. The tracking and mapping of geographically-distributed, dynamic sources of information require novel approaches to the solution of cooperative pursuit-evasion problems. Many of these underlying problems are known to be NP-complete. However, there is a need to develop clever heuristics to solve these problems. Further there is a need to design appropriate interfaces for human operator(s) to interact with and command the heterogeneous team.
The objective of the workshop is to bring together several experts in different disciplines interested in this problem, but who normally do not interact with each other. This will help create a new sub community in robotics that will open up new avenues for research and education. For example, group behaviors in biology may offer several directions of investigation as a starting point. Bio-inspired approaches to heterogeneity may offer insight that traditional, optimization-based approaches to control may not provide. On the other hand, new techniques in optimization and systems theory may offer practitioners new sub-optimal but efficient approaches to deployment. This workshop will feature a keynote talk, research presentations and discussions in these areas to report on the state-of-the-art in different related areas and to identify new directions for research.
Besides the organizers, there are the following speakers:
|
George Pappas Professor, Deputy Dean Department of Electrical and Systems Engineering, |
Magnus Egerstedt Associate Professor School of Electrical and Computer Engineering Georgia Institute of Technology |
|
John Clark Lockheed Martin |
Ali Jadbabaie Assistant Professor Department of Electrical and Systems Engineering |
|
Gaurav Sukhatme Associate Professor Computer Science Department |
Salah Sukkarieh Associate Professor ARC Centre of Excellence for Autonomous Systems Australian Centre for Field Robotics The |
|
Randy Beard Professor Electrical and Computer Engineering |
Jonathan How Professor Department of Aeronautics and Astronautics Aerospace Controls Laboratory Massachusetts Institute of Technology |
|
Bin Yu Quantum Leap Innovations, Inc. |
David Cole ARC Centre of Excellence for Autonomous Systems Australian Centre for Field Robotics The |
|
David Scheidt Johns |
Francesco Bullo Associate Professor Center for Control, Dynamical Systems and Computation |
8:40-9:00 Welcome and Opening Remarks [ slides ]
Vijay Kumar and Marc Steinberg
9:00-10:40 Sensing, Control and Coverage
Chair: Karl Hedrick
Active Decentralised Search, Track and Classification
in Natural Environments [ slides ]
Salah Sukkarieh
Graph-Based Control of
Heterogeneous Robot Networks:
From Controllability to Optimal Control [ slides ]
Magnus Egerstedt
Time-Optimal UAV Trajectory
Planning
for 3D Urban Structure Coverage [ slides ]
Peng Cheng
Visual Pose Estimation for
Aerial Robots: Implications for
Gaurav Sukhatme
10:40-11:00 Coffee Break
11:00-12:15 Distributed Systems
Chair: Vijay Kumar
Challenges and
Opportunities in Multi-Agent Systems
[ slides ]
George Pappas
Monotonic Target Assignment for Robotic Networks [ slides ]
Francesco Bullo
Optimization and Optimal Control of Spatially Distributed Systems [ slides ]
Ali Jadbabaie
Path Clearance with and without Multiple Scouting UAVs [ slides ]
Maxim Likhachev
12:40-14:00 Lunch Break
14:00-15:40 Deployment and Experimentation
Chair: Magnus Egerstedt
Robust Mission Planning
with Heterogeneous Vehicles using RAVEN [ slides
]
Jonathan How
Multi-agent Collaborative Flight Experiments [ slides ]
Karl Hedrick
Architectural Approaches to Autonomy Integration in UxVs [ slides ]
John Clark
Cooperative Perimeter Surveillance [ slides ]
Randy Beard
15:40-16:00 Coffee Break
16:00-17:15 A Dynamic, Distributed
Constraint Optimization Algorithm
for Dynamic Task Allocation among UAVs [ slides ]
Bin Yu
Decentralised Data Fusion
and Cooperative Control Demonstration
of Multiple UAVs for Feature Localisation [ slides ]
David T. Cole
Mission-level Autonomy for
Heterogeneous Unmanned
David Scheidt
17:15-18:00 Panel Discussion 2
Organization, structure and architecture for complex multi-UAV systems
Moderator: Marc Steinberg
1. Title: Active Decentralised Search, Track and Classification in Natural Environments
Presenter: Salah Sukkarieh
Abstract: In this talk I will present some of the steps we are taking in developing decentralised data fusion algorithms for the search, track, and classification of both natural and man-made features. The algorithms have been recently demonstrated in two separate field trials: the first is the active cooperative tracking of ground based features by a team of UAVs; the second is the mapping of a natural environment by a mixed system of UAV and ground based systems. Results from these trials will be presented as well as the research directions we are taking to include search and classification.
2. Title: Graph-Based Control of Heterogeneous Robot Networks: From Controllability
to Optimal Control
Presenter: Magnus Egerstedt
Abstract: Arguably, the overarching scientific challenge facing the area of networked robot systems is that of going from local rules to global behaviors in a predefined and stable manner. In particular, issues stemming from the network topology imply that not only must the individual agents satisfy some performance constraints in terms of their geometry, but also in terms of the combinatorial description of the (dynamic) network. Moreover, a multi-agent robotic network is only useful inasmuch as the agents can be redeployed and reprogrammed with relative ease, and we address these two issues (local interactions and programmability) from a controllability point-of- view. In fact, the problem of driving a collection of mobile robots to a given target destination is studied, and sufficient conditions are given for this to be possible, based on novel tools from algebraic graph theory.
3. Title: Time-Optimal UAV Trajectory Planning for 3D Urban Structure Coverage
Presenter: Peng Cheng
Abstract: Deployment of UAVs with onboard sensors and networks in mobile surveillance has become one of the fastest growing sectors in robotics. While a large amount of research has focused on the coverage problems in the planar suburb environments, there is an increasing demand for the coverage methods in the urban environment enabling the emerging applications of mobile surveillance systems in 3-D building reconstruction in Google Maps, city surveillance, and environment monitoring. In this talk, I will discuss the time-optimal trajectory planning of a sensor attached to an Unmanned Aerial Vehicle (UAV) to provide complete 3-dimensional coverage with applications to the urban environments with 2.5-dimensional features. The basic approach is to approximate the features of interest with a set of non planar coverage surfaces and to design a motion plan that guarantees the coverage surface is swept completely with a conical-field-of-view sensor. I establish a lower bound on time for a UAV to achieve complete coverage and derive the analytical coverage plan whose duration is a constant times this lower bound. Our hardware-in-the-loop simulation results verify the effectiveness of the proposed algorithm.
4. Title: Visual Pose Estimation for Aerial Robots: Implications for Cooperating UAVs
Presenter: Gaurav Sukhatme
Abstract: We discuss algorithms for estimating the pose of aerial robots using vision-based techniques. We give an overview of recent results in vision-based localization based on visual odometry wherein UAV motion is computed by tracking visual landmarks on the ground. We comment on the effect of changing camera angle and show experimental results using a robotic helicopter. We discuss implications for cooperative localization where vehicles on the ground could be used for accurately localizing small UAVs.
5. Title: Challenges and Opportunities in Multi-Agent Systems
Presenter: George Pappas
Abstract: The modern paradigm of mobile ad-hoc sensor networks as well as inspiring links to problems in biology, social behavior, statistical physics, and computer graphics have created a wealth of novel problems for the coordinated control and sensing of multi-agent systems. This is not only a tremendous intellectual opportunity for our community, but also a great technical challenge as we must embrace tools and algorithms from neighboring and distant fields. In this talk, I will present an array of new multi-agent problems that we have addressed in our group explaining flocking behavior by birds and resulting in algorithms for distributed consensus, to topology control as well as dynamic sensor placement and assignment using local coordination rules. The underlying critical theme of all the problems is the relationship between the global architectural interconnection topology and the local distributed controllers and estimators.
6. Title: Optimization and Optimal Control of Spatially Distributed Systems
Presenter: Ali Jadbabaie
Abstract: Spatially distributed dynamical systems are a general class of dynamic systems comprised of a large number of subsystems coupled either through their dynamics or through a common objective, shared cooperatively with other subsystems to achieve a global task. An inherent property of these systems is that their subsystems interact only with other subsystems in their (spatial) neighborhood. All subsystems are equipped with actuating, sensing, computing, and telecommunication capabilities. Communication is critical for cooperation to achieve the common objective. The underlying dynamics of such systems can be modeled as finite-dimensional systems with large vectors of state, input, and output variables which are indexed both in space and time. A graphic example of such systems include heterogeneous networks of unmanned vehicles.
In this talk, we study the locality features of optimal control for spatially distributed systems in which the influence of dynamics as well as the coupling in the cost function of other subsystems on a given system decays as a function of spatial distance. For example, the influence of neighboring systems could decay exponentially as a function of distance, or there could be an abrupt distance-based cut-off on impact of the state of one subsystem on other neighboring ones. Specifically, we study the trade-offs involved in guaranteeing that even the centralized solution of optimal control problems for such systems are inherently localized. Using tools from operator algebra, functional analysis and optimization theory, we show that the type of decay in coupling in dynamics and cost function is inherited in optimal control solutions. Similar results are also demonstrated for solutions of constrained finite horizon optimal control problems.
7. Title: Monotonic Target Assignment for Robotic Networks
Presenter: Francesco Bullo
Abstract: In this talk we look at a target assignment problem in which each robot has a limited communication range, a maximum speed, and knowledge of every target's position. The problem is to devise distributed algorithms that allows the robots to divide the target locations among themselves and, simultaneously, leads each robot to its unique target. We introduce a broad class of algorithms, called monotonic algorithms, for solving the problem and provide a lower bound on the completion time for all algorithms in the class. We propose two monotonic algorithms for this problem; one designed for ``sparse'' environments, in which communication between robots is infrequent, and one for ``dense'' environments, where communication is more prevalent. In the environment for which it was designed, we show that each algorithm's worst-case completion time is within a constant factor of the optimal monotonic algorithm.
8. Title: Path Clearance with and without Multiple Scouting UAVs
Presenter: Maxim Likhachev
Abstract: This talk presents the techniques that we have recently been developing in order to address the problem of path clearance. In the path clearance problem, a robot needs to reach its goal as quickly as possible without being detected by adversaries. The robot does not know the precise locations of adversaries, but has a list of their possible locations. Any of these locations can be sensed by the robot itself or any of the available scouting UAVs, and the robot can go through the location if no adversary is present or has to take a detour otherwise.
The problem of planning for path clearance is highly challenging since it involves both planning under uncertainty as well as planning for multiple agents. In addition, the size of a typical environment is several kilometers wide while its traversability is highly non-uniform. In the first part of the talk, we will introduce a notion of clear preferences on uncertainty and show how it can be used to develop an efficient algorithm, called PPCP, for planning under uncertainty when no scouts are present.
The algorithm is anytime, converges to an optimal solution under certain conditions and scales well to large-scale environments. In the second part of the talk, we will show several strategies for how to use the PPCP algorithm in case multiple scouting UAVs are available and show the benefits of these strategies experimentally.
9. Title: D-DCOP: A Dynamic, Distributed Constraint Optimization Algorithm for
Dynamic Task Allocation among UAVs
Presenter: Bin Yu
Abstract: Distributed task allocation is a popular topic studied by many researchers in AI and control theory. In this paper we explore the synergies between our previous token-based coordination algorithms and k-optimal distributed constraint optimization (DCOP) techniques such as distributed stochastic algorithm (DSA). We develop a dynamic, distributed constraint optimization algorithm (D-DCOP) for distributed and asynchronous task allocation in multi-robot systems. In D-DCOP, each vehicle exchanges the task information (encapsulated in tokens) with its neighbors and transfers the task to a neighbor if the neighbor has a higher utility for the given task. The effectiveness of the D-DCOP algorithm is demonstrated in a scenario of dynamic task allocation for heterogeneous UAVs with limited and intermittent communication.
10. Title: Robust Mission Planning with Heterogeneous Vehicles using RAVEN
Presenter: Jonathan P. How
Abstract: Many decision systems for autonomous agents rely on an accurate model description in order to provide a truly optimal system performance, and any model uncertainty will likely degrade this performance. This talk will discuss the problem of persistent surveillance missions with heterogeneous UAVs, where the vehicle heterogeneity is expanded to include unique vehicle capabilities and health management considerations. For example, one vehicle may have more uncertainty in the fuel burn rate, and thus may require more frequent refuelings than the others in the team. The talk will demonstrate how this uncertainty is captured in the planning problem and address the tradeoff between being robust and being overly conservative. This tradeoff will be illustrated with hardware experiments on the MIT ACL RAVEN testbed.
11. Title: Architectural Approaches to Autonomy Integration in UxVs
Presenter: John Clark
Abstract: As part of the Intelligent Control and Autonomous Replanning of Unmanned Systems (ICARUS) effort, an open architecture based approach was chosen as the method to integrating several components enabling autonomy among a heterogeneous set of UxVs. The presentation will address the pros and cons of the open architecture approach that were uncovered during the execution of the ICARUS program. The discussion will also include specific challenges faced and the methods used to overcome these challenges.
12. Title: Cooperative Perimeter Surveillance
Presenter: Randy Beard
Abstract: This talk will focus on the problem of cooperative perimeter surveillance using a team of small UAVs. We will focus on the scenario of tracking the perimeter of a moving forest fire. Fire surveillance is interesting because the perimeter is unknown a priori, but it is visually distinct and can therefore be tracked using an infrared camera. We will describe recent results on vision based perimeter surveillance. The fire surveillance problem is also interesting because the terrain may preclude communication between the team of UAVs, and between each UAV and the ground station. Therefore, a distributed cooperative control algorithm that only requires infrequent communication is needed. We will describe a very simple algorithm for cooperative perimeter surveillance and demonstrate its effectiveness through simulation and flight results.
13. Title: Mission-level Autonomy for Heterogeneous Unmanned Air Vehicle Teams
Presenter: David Scheidt
Abstract: This talk provides an overview of JHU/APL's research in cooperating unmanned vehicles. We have developed and successfully demonstrated heterogeneous unmanned vehicle teams. These teams respond to mission-level intelligence, surveillance and reconnaissance objectives by self-organizing to allocate tasking and coordinate within a specific task. Vehicles respond to asynchronous mission-level objectives provided by one or more users. The development of these unmanned vehicle teams required research in control, networking protocols, human-systems integration and horizontal data fusion. The control technique used to coordinate these vehicles is Dynamic Co-Fields (DCF), a behavior-based control technique. DCF coordination is decentralized, emergent and stigmergic. A routerless, delay-tolerant networking protocol is used to exchange information. This protocol uses monologues to generate a distributed blackboard which provides a basis to coordinated activities without requiring vehicle-to-vehicle dialogue. With this method vehicle response to environmental dynamics is both rapid and robust. This paper details the architecture and techniques used to develop unmanned vehicle teams that are composed of vehicles exhibiting a variety of mobility and sensing capabilities. Experimental results of as many as six unmanned air vehicles operating in complex (NP-Hard), dynamic real-world environments (>100 km2 operating area) and simulation-based results of large numbers of vehicles (>200 vehicles) are provided.
14. Title: Decentralised Data Fusion and Cooperative Control Demonstration of Multiple
UAVs for Feature Localisation
Presenter: David T Cole
Abstract: Flight tests conducted during September 2007 demonstrated Decentralised Data Fusion (DDF) and information theoretic Cooperative Control for feature localization. A team of UAVs performed a mission to cooperatively estimate the position and velocity states of a number of ground features. Information obtained from vision sensors is shared among the UAVs through a DDF network. An information based utility function allows UAVs to select which feature to observe next, and a dynamically plan a path to it. By communicating utilities the UAVs are able to cooperatively choose the optimal team action which maximizes the total information gained. Three separate scenarios were demonstrated, each with varying degrees of cooperation between the UAVs. They were no communication at all, DDF communications only, and DDF and Cooperative Control. Results are presented for each of the scenarios and a comparison made of the performance. It is shown that significant benefits can be gained through increased levels of cooperation.