Observation planning for Unmanned Aerial Vehicles (UAVs) is a challenging task as it requires planning trajectories over a large continuous space and with motion models that can not be directly encoded into current planners. Furthermore, realistic problems often require complex objective functions that complicate problem decomposition. In this paper, we propose a local search approach to plan the trajectories of a fleet of UAVs on an observation mission. The strength of the approach lies in its loose coupling with domain specific requirements such as the UAV model or the objective function that are both used as black boxes. Furthermore, the Variable Neighborhood Search (VNS) procedure considered facilitates the adaptation of the algorithm to specific requirements through the addition of new neighborhoods. We demonstrate the feasibility and convenience of the method on a large joint observation task in which a fleet of fixed-wing UAVs maps wildfires over areas of a hundred square kilometers. The approach allows generating plans over tens of minutes for a handful of UAVs in matter of seconds, even when considering very short primitive maneuvers.
We present the Limited-range Online Routing Problem (LORP), which involves a team of Unmanned Aerial Vehicles (UAVs) with limited communication range that must autonomously coordinate to service task requests. We first show a general approach to cast this dynamic problem as a sequence of decentralized task allocation problems. Then we present two solutions both based on modeling the allocation task as a Markov Random Field to subsequently assess decisions by means of the decentralized Max-Sum algorithm. Our first solution assumes independence between requests, whereas our second solution also considers the UAVs' workloads. A thorough empirical evaluation shows that our workloadbased solution consistently outperforms current state-of-the-art methods in a wide range of scenarios, lowering the average service time up to 16%. In the bestcase scenario there is no gap between our decentralized solution and centralized techniques. In the worst-case scenario we manage to reduce by 25% the gap between current decentralized and centralized techniques. Thus, our solution becomes the method of choice for our problem. Keywords: task allocation, unmanned aerial vehicles, max-sum, decentralized 1. Introduction Unmanned Aerial Vehicles (UAVs) are an attractive technology for largearea surveillance . Today, there are readily available UAVs that are reasonably cheap, have many sensing abilities, exhibit a long endurance and can communicate using radios. UAVs have traditionally been controlled either remotely or by following externally-designed flight plans. Requiring human operators for each UAV implies a large, specialized and expensive human workforce. Likewise, letting UAVs follow externally prepared plans introduces a single point of failure (the planner) and requires UAVs with expensive (satellite) radios to maintain continuous communication with a central station. These constraints are acceptable in some application domains, other applications require more flexible techniques. For instance, consider a force of park rangers tasked with the surveillance of a large natural park. Upon reception of an emergency notification, the rangers must assess the situation as quickly as possible.
The emerging area of intelligent unmanned aerial vehicle (UAV) research has shown rapid development in recent years and offers a great number of research challenges for artificial intelligence and knowledge representation. Much previous research has focused on low-level control capability with the goal of developing controllers which support the autonomous flight of a UAV from one way-point to another. The most common type of mission scenario involves placing sensor payloads in position for data collection tasks where the data is eventually processed off-line or in real-time by ground personnel. Use of UAVs and mission tasks such as these have become increasingly more important in recent conflict situations and are predicted to play increasingly more important roles in any future conflicts. Intelligent UAVs will play an equally important role in civil applications. For both military and civil applications, there is a desire to develop more sophisticated UAV platforms where the emphasis is placed on development of intelligent capabilities and on abilities to interact with human operators and additional robotic platforms. Focus in research has moved from low-level control towards a combination of low-level and decision-level control integrated in sophisticated software architectures.
At Berkeley we have been interested in design schemes for network of complex networks of semi-autonomous agents. These networks are characterized by interaction between discrete decision making and continuous control. The control of such systems is often organized in hierarchical fashion to obtain a logarithmic decrease in complexity associated with the design, We have used as examples three classes of systems to motivate the design approach: 1. Intelligent Vehicle Highway Systems (IVHS) 2. Air Traffic Management Systems (ATMS) 3. Unmanned Aerial Vehicles Over the last five years or so, a group of us have developed a set of design approaches which are aimed at designing control schemes which are live, deadlock free, and "safe". Our design methodology is to be considered an alternative to the verification based approaches to hybrid control systems design, and is an interesting blend of game theoretic ideas, fault handling in a probabilistic framework, mathematical and temporal logic and planning ideas from robotics. In this talk, I will focus on design problems involved in coordinating groups of Unmanned Aerial Vehicles (UAVs).
We present a methodology for the deployment of the max-sum algorithm, a well known decentralised algorithm for coordinating autonomous agents, for problems related to situational awareness. In these settings, unmanned autonomous vehicles are deployed to collect information about an unknown environment. Our methodology then helps identify the choices that need to be made to apply the algorithm to these problems. Next, we present a case study where the methodology is used to develop a system for disaster management in which a team of unmanned aerial vehicles coordinate to provide the first responders of the area of a disaster with live aerial imagery. To evaluate this system, we deploy it on two unmanned hexacopters in a variety of scenarios. Our tests show that the system performs well when confronted with the dynamism and the heterogeneity of the real world.