|
AeroAstro HighlightThe following article appears in the 2010–2011 issue of AeroAstro, the annual report/magazine of the MIT Aeronautics and Astronautics Department. © 2011 Massachusetts Institute of Technology. THINKING FOR THEMSELVES
|
|||||||||||
 |
Aerospace Controls Lab Ph.D. students Josh Redding (left) and Buddy Michini monitor an autonomous quadrotor positioning itself to land on a battery recharge station. As soon as it perches on the landing platform (just above the green circuit board in the center) a fresh battery will slide into the vehicle from the rotating carousel on the right, the drained battery will slide into the carousel on the left for recharging, and the vehicle will take off to continue its mission. The system enables long duration surveillance missions with minimal human support. (Wiliam Litant/MIT photo) |
The reader may be familiar with autonomous vehicles, such as the Roomba vacuum cleaning robot, that perform fairly simple tasks in constrained environments — but the goals of this work are to develop much smarter robots that can operate in, and adapt to, the dynamic and complex world familiar to humans. This includes examples such an autonomous car that optimizes its route to a pick-up point to avoid traffic tie-ups reported by other vehicles, while designing motion paths that avoid potentially erratic maneuvers by pedestrians, cyclists, and other cars. It could also include a team of UAVs collaborating to choose the best locations to sample the atmosphere to better predict a storm’s path.
From choosing which actions to take, to deciding which maneuvers to execute to perform those actions, planning is a crucial part of optimizing the solution to the fundamental questions of “what, where, when, how?” Of course, to operate in a dynamic world, this planning must be fast enough that it can be performed online, in real-time. The result is similar to classical feedback control, in which sensors provide information about the motion of the system, and then use the information to compute corrective inputs. But, autonomy extends that framework to include both continuous and discrete decisions, such as activity planning, compliance to rules of behavior, and trajectory design.
There are numerous challenges to achieving these goals, such as developing planning algorithms that are both computationally tractable and communication-efficient, adapting the autonomous systems to interact in a synergistic and trustworthy fashion with human operators, and handling uncertainty in the location, motion, and intent of other objects.
The research groups led by MIT Aeronautics and Astronautics Professors Emilio Frazzoli, Jonathan P. How, and Brian Williams have developed several new approaches to address the computational complexity challenges inherent in both trajectory design and activity planning.
 |
 |
In the photograph (left), the autonomous forklift navigates around cones and palletized cargo. The generated image (right) depicts the activity as viewed by the autonomous planner, which identifies a tree of feasible paths and selects a safe trajectory (magenta) to maneuver around the perceived obstacle field (red, with black penalty regions) to reach the goal position (green). |
Trajectory planning in an environment with constrained dynamics and obstacles is a complex problem, even for guiding a single vehicle. Numerous approximate solutions have been developed over the years using a variety of different strategies. One approach, called sampling-based planning, is particularly attractive because it scales well with the problem size and provides a systematic method of exploring the environment for a feasible path, while, at the same time, refining any path to the goal that may have been found. Key amongst these algorithms is the Rapidly-Exploring Random Tree (RRT) that has proven to be a successful approach for designing safe trajectories for autonomous systems.
MIT DARPA Urban Challenge team members How and Frazzoli built on this success to develop the Closed-loop Rapidly-Exploring Random Tree (CL-RRT) algorithm to address the challenges of planning paths for an autonomous car with unstable and nonlinear dynamics. The algorithm was successfully demonstrated at the 2007 DARPA Urban Challenge, which was held from October 26 though November 3rd in Victorville, Calif. MIT developed a unique autonomous vehicle: Talos, a Land Rover LR3 equipped with a diverse range of lidar, vision, radar, and navigation sensors connected to a powerful blade cluster computer system. The MIT vehicle employed novel algorithmic approaches to perception, planning, and control for the challenging task of autonomous driving in uncertain, dynamic environments. The vehicle was one of 35 that participated in the DARPA Urban Challenge National Qualifying Event, and, based on our performance there, was one of 11 teams to qualify for the Urban Challenge Event based on our performance. The vehicle was one of only six teams to complete the race, finishing in fourth place.
Through the addition of a path-tracking control loop in the system’s RRT prediction model, CL-RRT has achieved accurate tracking of predicted trajectories. This feedback control loop also enables a more efficient RRT sampling strategy, so that a single input to the closed-loop system can create a long, dynamically feasible, trajectory (on the order of several seconds) while the controller provides a high-rate stabilizing feedback to the vehicle. While RRTs are effective and versatile, they provide no performance guarantees. In fact, recent work has shown that they are guaranteed not to converge to the best path. However, members of the Aerospace Robotics and Embedded Systems Laboratory, led by Frazzoli, have developed a modification to the standard RRT algorithm that ensures asymptotic optimality; that is, that the planner will find the best answer given sufficient time. The resulting RRT* algorithm shows that, under a number of technical assumptions, probabilistic convergence to the cost-optimal trajectory can be obtained.
RRT* provides a systematic means of planning paths amongst static and/ or predictably-moving obstacles, but planning safe paths around objects with poorly known or unpredictable paths poses a new set of challenges. Anyone who has driven through an intersection at night or in poor weather is familiar with the typical problems: Where are the lines or edge of the road? What are the expected paths of the other vehicles? Are they all good drivers? Do they know and obey the rules of the road?
Jonathan P. How and Emilio Frazzoli’s novel algorithmic approaches to perception, planning, and control, used in conjunction with a range of lidar, vision, radar, and navigation sensors and a blade cluster computer system piloted this Land Rover to fourth place in the 2007 DARPA Urban Challenge. (Jonathan P. How/MIT photo) |
 |
To address the uncertainty in the vehicle path or the location of obstacles, members of the Aerospace Controls Laboratory led by How developed the Chance- Constrained Rapidly-Exploring Random Tree (CC-RRT) algorithm. In addition to maintaining the benefits of RRT algorithms, CC-RRT uses chance constraints to ensure that all constraints are satisfied with some minimum probability. This is known as “probabilistic feasibility.” In environments where absolute safety may be unrealistic, this allows the user to specify exactly how much risk is acceptable. The approach has been demonstrated to efficiently compute risk-aware trajectories for a variety of dynamics in complex, cluttered environments. The lab is now applying this approach to an autonomous parafoil to robustly avoid terrain in the presence of uncertain wind conditions.
Autonomous underwater vehicles (AUVs) are also being developed to enable long-term autonomous exploration of previously uncharted portions of the ocean, but performing these extended missions can be risky. For example, due to a sudden drift in current, an AUV can collide with a seamount if it moves too close to the sea floor while mapping a treacherous canyon. A seasoned submarine commander would be skilled at identifying navigation paths that maximize scientific value, while operating within acceptable levels of risk. The Model-Based Embedded and Robotic Systems Research group led by Williams has developed robust, chance-constraint planning algorithms that automatically navigate vehicles to achieve user specified science goals, while operating within risk levels specified by the operator. These algorithms operate by iteratively allocating the user specified risk to different steps in the mission plan, until a risk allocation is found that maximizes science utility. This approach was used to navigate a vehicle to map portions of Monterrey Bay during January 2008, and is currently being applied to the navigation of an autonomous personal air vehicle.
To handle uncertainty in the motions of other vehicles, ACL members developed a novel trajectory prediction approach that infers, in real-time, the intentions of the other agents in the environment, and embeds these in the calculations of the estimated reachability sets to obtain a probabilistic description of their future paths. Gaussian Processes provide an efficient means for encoding these intents, and the developed RRT-Reach algorithm efficiently computes the reachability sets, which are guaranteed to obey dynamic feasibility and avoid static obstacles. This greatly increases the accuracy of the prediction. The utility of the resulting RR-GP approach was demonstrated on the CC-RRT probabilistic planner by significantly increasing the safety of the planned paths in the presence of dynamic agents with uncertain intentions.
Activity planning for multiple agents introduces many challenges. Typical problems involve a networked team of heterogeneous assets (manned/autonomous, air/ground, etc.) performing numerous tasks with temporal and logical constraints — and thus, there are many ways to accomplish mission goals. ARES developed techniques to formulate mission specifications in an expressive, yet natural, formal language such as Linear Temporal Logic (LTL). This includes Boolean operators (“and,” “or,” “not”), and temporal operators (“always,” “eventually,” “until,” “unless,” etc.), which are sufficiently expressive to capture many missions of interest. This work also led to a novel automated, systematic procedure to convert LTL specifications into a mathematical program, which enables an efficient solution through COTS software. ARES has also developed an RRT-like sampling-based algorithm, called RRG, to compute trajectories that are feasible with respect to a language called mμ-calculus, which is strictly more expressive than LTL.
ACL developed a novel distributed task allocation planner (CBBA) with provable convergence and performance guarantees. CBBA builds on recent work associated with analyzing the flow of information in social networks (e.g., “gossip” algorithms), but focuses on agreement of plans rather than just information, which has proven to be more communication efficient for the planning problem. CBBA can handle time windows of task validity, time-varying networks, coordination constraints between agents to perform tasks, and asynchronous formulations that are better adapted for real-world implementation. These additions make CBBA a very general framework that can be used to do predictive planning in real-time with nonlinear cost functions, and realistic vehicle dynamics for heterogeneous agents. CBBA has been experimentally tested using indoor flight facilities, and outdoor flight-testing will continue.
Uncertainty remains a ubiquitous feature of robotics applications and a key research challenge that potentially limits their deployment. There are, of course, many types of uncertainty, which can be roughly characterized as either internal (e.g., models) or external (e.g., wind). When the robots experience problems as a result of incorrect models or impact of disturbances, the agents can re-plan in light of new information. However, it is likely that the initial, incorrect decisions will have consumed resources (e.g., fuel, power), and may even have positioned agents in dangerous states where they are unable to respond effectively to the new information. Thus, in constructing their initial plan, the agents should hedge against their uncertainty, and select robust plans that “expect the unexpected.”
A key challenge here is that embedding the models required to accurately predict the stochastic environment typically leads to computationally intractable planning problems. This suggests the use of simplified/abstracted models; however, this can lead to suboptimal (possibly catastrophic) performance. Furthermore, the parameters of these models are typically not well known, leading to additional uncertainty.
ACL developed computationally tractable techniques to improve the robustness (e.g., improve the worst case performance) of the planning algorithms. Recent success in this area includes Dirichlet Sigma Point Sampling, which provides a framework for reducing the number of scenarios required to accurately predict the worst-case performance. ACL is also pursuing a second approach that is similar to traditional adaptive control in that it has both direct (i.e., learns better plans to execute) and indirect (i.e., learns better estimates of the model to plan with) algorithms. Challenges in this case are that learning in large state spaces is slow, memory intensive, and computationally demanding.
Recent successes here include incremental Feature Dependency Discovery (iFDD) and intelligent Cooperative Control Architecture (iCCA). The iCCA research has focused on developing algorithms to improve planner performance over time in the face of uncertainty and a dynamic world. Our approach augments the “safe” plans calculated by a standard planning module such as CBBA, and analyzes the past performance to incrementally adapt the policy to maximize future cumulative rewards. The integrated framework has been shown to boost solution optimality by an average of 10% in numerical trials, and ongoing work is investigating the performance improvements experimentally.
Learning methods often use a linear function approximation of the value function, a key component needed for the planner to determine the best actions to take. A classic challenge with function approximation techniques is how to select the set of basis functions with cheap computational complexity in large planning problems. Given an initial set of features, iFDD expands the set of basis in areas where approximation error persists. iFDD is simple to implement, fast to execute, and can be combined with any online learning technique. This technology allows for planning under uncertainty in real-life situations. For example, after an earthquake, a team of UAVs can commence a collaborative search and rescue mission in the disastrous area where the location and number of survivors are estimated based on satellite images.
The level of autonomy demanded of unmanned air, ground, and underwater vehicles by civilian and military operations is increasing steadily. The underlying algorithms must be able to operate effectively over long distances, for long durations, and with very little prior information. As one example of the future for autonomous systems, AeroAstro researchers are collaborating on a project to automate the operation of an aircraft carrier deck, developing novel algorithms for scheduling launch sequences, moving aircraft safely across the deck, and robust operation in rapidly changing and uncertain battle environments. These algorithms depend on theoretical advances in activity and trajectory planning and learning under uncertainty, which lie at the heart of the Department’s research in autonomy. We anticipate that these technologies will also play a critical role in developing the autonomous cars of the future.
Jonathan P. How is the MIT Richard Cockburn Maclaurin Professor of Aeronautics and Astronautics. Prior to joining the MIT faculty in 2000, he was an assistant professor in the Department of Aeronautics and Astronautics at Stanford University. Research interests in the design and implementation of distributed robust planning algorithms to coordinate multiple autonomous air/ground/space vehicles in dynamic uncertain environments. Jon How may be reached at jhow@mit.edu.
Emilio Frazzoli is an associate professor in the MIT Aeronautics and Astronautics Department. Previously, he was an officer in the Italian Navy, a spacecraft dynamics specialist at Telespazio S.p.A. in Rome and a faculty member at the University of Illinois at Urbana Champaign and at the University of California, Los Angeles. His main research interests are aerospace control systems, autonomous air/space/ground vehicles, mobile robotics and transportation networks. Emilio Frazzoli may be reached at frazzoli@mit.edu.
Brian Williams is a professor and the undergraduate officer in the MIT Aeronautics
and Astronautics Department where he leads the Model-based Embedded and Robotic Systems group. His research interests include space and aerial robotics, cognitive robotics, automated reasoning and artifi cial intelligence, automation for operations and design, hybrid control systems, robot coordination, and energy management. Brian Williams may be reached at williams@mit.edu.
 |
 |
     |
