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
Demonstration: Cooperative Model Predictive Control
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
Conference Paper: Path-Planning with Avoidance using Nonlinear Branch-and-Bound Optimisation
Eele, A. & Richards, A.G. Path-Planning with Avoidance using Nonlinear Branch-and-Bound Optimisation, AIAA Guidance, Navigation and Control Conference, 2007
Abstract:
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 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.
Conference Paper: Efficient Path Optimization with Terrain Avoidance
G. Keith, J. Tait and A. G. Richards, "Efficient Path Optimization with Terrain Avoidance," AIAA Guidance, Navigation and Control Conference, August 2007.
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.
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
Journal Paper: Distributed Robust Receding Horizon Control for Multi-vehicle Guidance
Kuwata, Y.; Richards, A.G.; Schouwenaars, T. & How, J.P., Distributed Robust Receding Horizon Control for Multi-vehicle Guidance, IEEE Transactions on Control Systems Technology, Vol. 15, No. 4, July 2007, Pages 627--641.
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.
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
Conference Paper: Robust Receding Horizon Control using Generalized Constraint Tightening
Y. Kuwata, A. G. Richards, and J. P. How, Robust Receding Horizon Control using Generalized Constraint Tightening, American Control Conference, 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.
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
Conference Paper: Robust Distributed Model Predictive Control with Cooperation
P. Trodden and A. G. Richards, "Robust Distributed Model Predictive Control with Cooperation", European Control Conference, 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 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.
Conference Paper: Robust Multiplexed Model Predictive Control
A. G. Richards, K.-V. Ling and J. M. Maciejowski, Robust Multiplexed Model Predictive Control, European Control Conference, 2007.
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.
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
Project: Robust Model Predictive Control
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
Project: Autonomous Vehicle Testbed
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.
PhD Project: Cooperative Distributed Model Predictive Control
PhD Student Paul Trodden, supported by EPSRC and BAE Systems
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.
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.
PhD Project: Optimisation of Aircraft Taxi Operations
PhD Student Gillian Keith, supported by EPSRC and Airbus UK. This project is part of the Knowledge Transfer Network for Industrial Mathematics.
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
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
PhD Project: Branch-and-Bound Optimisation for Collision Avoidance
Project by PhD Student Alison Eele, supported by EPSRC
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
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
Subscribe to:
Posts (Atom)