Cooperative control of autonomous systems

There may be nearly as many definitions for an autonomous system as there are scientists and engineers who research them. No standard definition exists within the research community, so the term often has an ambiguous meaning. Most researchers would agree that autonomy of any system can be thought of as existing on a continuum, with zero representing the lack of any autonomy and one representing complete autonomy. Without delving into the theoretical implications of these boundaries, it suffices to say that all current autonomous systems lie somewhere between these extremes. Many even argue that the correct term should be semi-autonomous system. Nevertheless, for the purpose of this special issue an autonomous system is considered to be a collection of agents that are endowed with an objective, receive and process inputs with some non-zero level of assistance, and execute assignments based on decisions made in whole or in part by the agents themselves. The autonomous systems considered in the research presented in this special issue generally consist of the following: a group of unmanned aerial/ground/underwater vehicles (UXV), a communication architecture, one or more control stations that process information and one or more human operators.

The use of UXVs in military missions has grown exponentially over the last 15 years or so, but interest in them in the research community goes back centuries, one could argue, to da Vinci and Tesla. Modern robotics has concentrated research toward artificial intelligence and autonomous systems. There are many extraordinarily difficult problems that are still open. Among those are problems such as information flow through the communication architecture, sensor path planning to maximize information gain and decision making with uncertainty. These are exactly the topics being researched by AFRL's Control Science Center of Excellence and by the many scientists and engineers who collaborate with them. The papers in this special issue represent a small sample of the research being conducted by this growing research community. Each paper is authored by researchers who regularly collaborate with the Air Force on the previously mentioned topics in outer-loop control of UXVs.

Jackson et al. 1 develop a graph search heuristic and use it on a task assignment problem that has a nonlinear objective function and task precedence constraints. The search heuristic used is a combination of two existing search heuristics: the Lin–Kernighan variable k-opt exchange heuristic and the Tabu search metaheuristic. The combined heuristic is compared to a branch and bound optimal tree search method on a collection of constrained and unconstrained task assignment problems. Simulations show that acceptable suboptimal assignments are achieved with multiple orders of magnitude less computation than that needed for the branch and bound tree search.

Karaman and Frazzoli 2 develop a novel algorithm for computing UAV assignments for a generalized vehicle routing problem known as the Vehicle Routing Problem with Linear Temporal Logic specifications (VRPLTL). A systematic procedure is described that converts an LTL mission specification into a set of constraints that are suitable to a mixed-integer linear program (MILP). The network flow and the set covering formulations of the MILP are both described in detail for the VRPLTL. Multiple mission planning examples are described, and results are presented that compare the relative strengths and weaknesses of these two different MILP formulations of the VRPLTL.

Krishnamoorthy et al. 3 use approximate dynamic programming techniques to construct suboptimal policies for UAVs engaged in a perimeter surveillance control problem. State space aggregation is used to lessen the effects of the curse of dimensionality which often renders many combinatorial optimization problems computationally intractable. Bounds are provided that assess the quality of the approximation, and a collection of numerical examples are solved with increasing levels of aggregation to illustrate the reduction in computational burden.

Powel and Morgansen 4 derive performance bounds for a group of autonomous vehicles obeying a nonlinear motion control model. The derived bounds represent the worst-case increase in separation between vehicles in the group performing a heading alignment maneuver using the Kuramoto oscillator as a controller. Monte–Carlo simulations with random initial headings are performed to analyze the communication energy required for the convergence of the discrete-time system. The results suggest a strategy for designing minimum communication energy algorithms for heading alignment and coordination for vehicles in which communication is relatively energetically expensive.

Casbeer and Holsapple 5 investigate a column generation technique as a distributed method for solving task assignment problems with precedence constraints. With a careful division of the overall team problem into small local problems, the column generation approach iteratively solves the sub-problems in a distributed way to reach an overall optimum. Owing to the complexity introduced by the precedence constraints, they conclude that it is unlikely that column generation alone would be practical for distributed task assignment but could perhaps be used in conjunction with other methods or a hierarchical design to allow sub-groups to solve smaller sized problems.

Doshi et al. 6 develop approximation algorithms and their bounds for Hamiltonian path problems for two heterogeneous vehicles. The approach involves two steps: finding the set of targets that each vehicle will be responsible for and then finding the optimal route for visiting those targets. The problem of partitioning is tackled by solving a linear program obtained by relaxing some of the constraints of an integer programming model for the problem, and the sequencing problem is solved either by Hoogeveen's algorithm or by the Lin–Kernighan heuristic to yield an approximately optimal solution. Bounds are given for the approximate algorithms, and the average quality of solutions given by the heuristics are found to be within 4% of the optimum.

Mellish et al. 7 use a backstepping control design to realize group coordination for vehicles in a flow field (e.g. wind, currents). This extends the group coordination strategy that was designed with first-order rotational dynamics to the second-order case. Controllers for both parallel and circular formations in the presence of a steady, uniform flowfield are derived. These controls extend prior results to a more realistic vehicle model. Aside from the addition of new sensing and communication requirements, the second-order control laws are demonstrated to have comparable performance to the first-order controllers.

Obermeyer et al. 8 present a distributed algorithm for a group of robotic agents to deploy into nonconvex polygonal environments with holes. Agents begin deployment from a common point, possess no prior knowledge of the environment, and operate only under line-of-sight sensing and communication. The objective of the deployment is for the agents to achieve full visibility coverage of the environment while maintaining line-of-sight connectivity with each other. Convergence and complexity statements are proven and presented alongside compelling simulation results.

We thank the editors of International Journal of Robust and Nonlinear Control for hosting this special issue, especially Mike Grimble, for his support and guidance. This work was performed in collaboration with the Control Science Center of Excellence of the Air Force Research Laboratory.