Convexification and Real-Time Optimization for Optimal Autonomous Joint Task and Path Planning
Abstract
Statement of Work:The objective of the proposed research is to develop an analytical and numerical framework to reliably solve complex real-time optimal Joint Task and Path Planning problems onboard autonomous single or multi-vehicle systems.Objective:The objective of the proposed research is to develop an analytical and numerical framework to reliably solve complex real-time optimal Joint Task and Path Planning (JTPP) problems onboard autonomous single or multi-vehicle systems. The proposed effort will develop new methods for the convexification of optimal control and parameter optimization problems associated with JTPP.Convexification is at the core of our formulation and it is particularly important since it facilitates the use of fast and trustworthy numerical optimization methods (convex optimization) in solving JTPP problems. Leveraging from the PI s recent advances in convexification and real-time custom convex optimization, he proposes to develop robust onboard solution methods for complex JTPP problems.Approach:The proposed research will tackle these challenges and provide the necessary algorithmic capabilities by progressing in two complementary research thrusts.- Thrust I - Convexification and Mixed Integer Convex Programming Formulation of JTPP: What are the set of nonconvex problem constraints that can be convexified with quantifiably minimal or no loss of optimality - Can the rest of the non-convex constraints be captured effectively using a small to moderate number of binary variables- Leveraging from the PI s recent advances in lossless convexification of non-convex path planning problems, this thrust aims to produce analytical results to formulate JTPP problems as real-time tractable Mixed Integer Convex Programming (MICP) problems. The formulations will keep the number of binary variables to a minimum and will lead to custom Branch and Bound (B&B) methods together with custom convex optimizationmethods to enable real-time tractability of the resulting MICP problems.- Thrust II - Development of robust, custom, real-time optimization algorithms: What are the challenges in adapting modern Interior Point Method (IPM) algorithms of convex optimization together with B&B to solve the MICP problems for real-time solutions of JTPP? How can we automate the IPM customization process and B&B methods as the JTPP problem structure and parameters change during a mission. This thrust aims to develop robust onboard implementable B&B and IPM algorithms customized for real-time JTTP solutions. The algorithm customization aims to increase thecomputational speed by 2-3 orders of magnitude relative to generic algorithms by exploiting specific problemstructures. Such computational speedups will enable the real-time solution of these MICP problems for JTPP. Since the customization can be done systematically, the PI aims to automate this process for real-time use. This capability will enable the automated customization of the optimizers to handle the changes in the JTPP problem structure caused by varying mission parameters, ultimately resulting in a resilient and adaptive onboardsolution capability for JTPPs.Overall Merit and ONR Mission/Relevance:Using optimization in a real-time, onboard settting will require significant innovation and customization of the algorithms in order to reliably solve these complex Joint Task and Path Planning problems. The proposed effort will develop new and scientifically innovative methods for the convexification of optimal control and parameter optimization problems associated with JTPP.The Navy has great interest in autonomous vehicles. The objective of the proposed research is to develop an analytical and numerical framework to reliably solve complex real-time optimal Joint Task and Path Planning problems onboard autonomous single or multi-vehicle systems.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Aug 08, 2016
- Source ID
- N000141612318
Entities
People
- Behçet Açıkmeşe
Organizations
- Office of Naval Research
- United States Navy
- University of Washington