The movie illustrates the branch-and-bound search process, finding the shortest route from the start (left) to the goal (green star, right) avoiding the obstacles (red circles). The vehicle has speed and turn rate limits. The result is globally optimal, but it is not necessary to search all combinations of "left and right".
Thursday, 13 September 2007
The movie demonstrates the difference between ordinary "greedy" DMPC and cooperative DMPC. Two vehicles must pass to reach their targets (circles) but the passage is too narrow. Beginning with greedy DMPC, the two vehicles reach a deadlock, but when they switch to cooperative DMPC, the deadlock is broken and both reach their targets.
Saturday, 18 August 2007
This paper describes a novel method for finding optimal trajectories for a vehicle constrained to avoid fixed obstacles. The key property of the method is that it provides globally optimal solutions to these non-convex problems while retaining the full nonlinear dynamics model. Applications for the new algorithm include the guidance of Uninhabited Aerial Vehicles, air traffic control, and path-planning for robots. The core concept is the direct application of branch-and-bound optimisation, tailored to suit avoidance problems by exploiting two new ideas: first, using a geometric branching strategy based on the decision of whether to pass an obstacle on the left or on the right; and second, solving the resulting subproblems by constructing simple solutions on each chosen "side'' and using them as the initial guesses for primal-dual optimisation techniques. Examples are provided to illustrate the branch-and-bound procedure and show successful determination of optimal paths. A comparison between the initial implementation of the method and an existing Mixed-Integer Linear Programming (MILP) approach is also presented. The results of the solve time comparison indicate in the majority of cases the proposed method was faster than the MILP approach.
Abstract: This paper presents a new algorithm for optimal path planning subject to terrain avoidance constraints. The new method extends an existing approach based on Mixed-Integer Linear Programming (MILP) to offer significant improvements in computational efficiency, while guaranteeing globally optimal solution of the path-planning problem. This improvement is the result of three key enhancements. First, the terrain representation is reformulated as a piecewise affine function, resulting in a better conditioned MILP problem. Second, an efficient method of approximating and simplifying real terrain data is developed. Finally, an iterative MILP solution approach is adopted, reducing computational effort by avoiding the application of redundant constraints. The new method is shown to offer significant reductions in solution time for only small loss of performance in terms of the planning objective.
Sunday, 15 July 2007
Abstract: This paper presents a new distributed robust Model Predictive Control algorithm for multi-vehicle trajectory optimization and demonstrates the approach with numerical simulations and multi-vehicle experiments. The technique builds on the robust-safe-but-knowledgeable (RSBK) algorithm, which is developed in this paper for the multi-vehicle case. RSBK uses constraint tightening to achieve robustness to external disturbances, an invariant set to ensure safety in the presence of changes to the environment, and a cost-to-go function to generate an intelligent trajectory around known obstacles. The key advantage of this RSBK algorithm is that it enables the use of much shorter planning horizons while still preserving the robust feasibility guarantees of previously proposed approaches. The second contribution of this paper is a distributed version of the RSBK algorithm, which is more suitable for real-time execution. In the distributed RSBK (DRSBK) algorithm, each vehicle only optimizes for its own decisions by solving a subproblem of reduced size, which results in shorter computation times. Furthermore, the algorithm retains the robust feasibility guarantees of the centralized approach while requiring that each agent only have local knowledge of the environment and neighbor vehicles’ plans. This new approach also facilitates the use of a significantly more general implementation architecture for the distributed trajectory optimization, which further decreases the delay due to computation time.
Sunday, 8 July 2007
Abstract: This paper presents a decentralized robust Model Predictive Control algorithm for multi-vehicle trajectory optimization. The algorithm is an extension of a previous robust safe but knowledgeable (RSBK) algorithm that uses the constraint tightening technique to achieve robustness, an invariant set to ensure safety, and a cost-to-go function to generate an intelligent trajectory around obstacles in the environment. Although the RSBK algorithm was shown to solve faster than the previous robust MPC algorithms, the approach was based on a centralized calculation that is impractical for a large group of vehicles. This paper decentralizes the algorithm by ensuring that each vehicle always has a feasible solution under the action of disturbances. The key advantage of this algorithm is that it only requires local knowledge of the environment and the other vehicles while guaranteeing robust feasibility of the entire fleet. The new approach also facilitates a significantly more general implementation architecture for the decentralized trajectory optimization, which further decreases the delay due to computation time.
Sunday, 1 July 2007
Abstract: This paper extends a form of distributed model predictive control (MPC) for subsystems with decoupled dynamics and with coupled constraints. By use of an objective function that includes knowledge of the coupling between subsystems, cooperative behaviour is promoted with respect to the global objective. The method is robust to persistent disturbances, by the use of the Tube MPC concept, in which an optimization designs a sequence of invariant state sets for the system to follow, rather than a trajectory. Robust stability is guaranteed for any choice of update sequence and objective function. It is demonstrated that, through cooperation, global performance can improve on that obtained by a simple distributed implementation.
Abstract: This paper extends the recently developed multiplexed model predictive control (MMPC) concept to ensure satisfaction of hard constraints despite the action of persistent, unknown but bounded disturbances. MMPC uses asynchronous control moves on each input channel instead of synchronised moves on all channels. It offers reduced computation, by dividing the online optimisation into a smaller problem for each channel, and potential performance improvements, as the response to a disturbance is quicker, albeit via only one channel. Robustness to disturbances is introduced using the constraint tightening approach, tailored to suit the asynchronous updates of MMPC and the resulting time-varying optimisations. Numerical results are presented, involving a simple mechanical example and an aircraft control example, showing the potential computational and performance benefits of the new robust MMPC.
Thursday, 15 March 2007
The figure on the right shows sets of velocity (Y-axis) vs position (X-axis). The blue region contains all the points from which an MPC planning problem can be solved. The purple region contains all the points that can be reached from the blue. Because the purple is inside the blue, the controller is robustly feasible - the state will always stay inside the blue. The controller being investigated here can be used for simple vehicle control problems. This result is part of on-going research on designing robust controllers.
View all news from this project
These robot vehicles are being developed for use in future projects. Rovers like these are used for testing and development of vehicle control algorithms. They have on-board computers, wireless network communications, and position sensing capability. They also have room for future upgrades including fitting on-board cameras or GPS for outdoor operations.
Decentralized Model Predictive Control solves a separate planning problem for separate subsystems but ensures satisfaction of coupled constraints. Breaking up the problem results in a five-fold reduction in computation time, compared to solving a single planning problem for the team. In the figure on the right, eight aircraft use DMPC to solve a conflict situation and all reach their goals successfully without colliding. Thanks to a new cooperation strategy, no one aircraft takes a "greedy" route that would disadvantage all others.
Future growth of air traffic demands faster air-to-gate-to-air transit at airports and the ICAO Advanced Surface Movement Guidance Control System specifically identifies the "routing" function as an opening for future autonomous operation. This project aims to apply advanced, robust, non-convex optimisation tools to the taxi routing problem, in order to reduce transit times, increase throughput capacity, and improve safety. For the latter, uncertainty will be considered explicitly, employing robust control and optimisation techniques. Furthermore, the project will investigate the computation, sensing and communication network infrastructure involved in this approach and will identify the functions and capabilities required on board each aircraft.
View all news from this project
This research involves a new approach to finding globally optimal solutions to avoidance problems, including UAVs avoiding radar threats and civil aircraft avoiding each other in free flight ATM. It should be faster than existing methods, because it can incorporate geometric knowledge in the optimisation algorithm instead of buying an expensive "black box" optimiser. It can also include more realistic, nonlinear dynamics models. Furthermore, we will research "hot start" methods for updating paths in the light of new information. Most existing work in this area simply restarts the optimisation from scratch.
View all news from this project