Novel Data-Driven Algorithms for Autonomous Vehicle Path Planning Problems with Uncertain Data Parameters

Project Team

Principal Investigator

Saravanan Venkatachalam, Wayne State University Manish Bansal, Virginia Tech

Government

Joseph Lee, Jonathon Smereka, Ground Vehicle Robotics, U.S. Army CCDC GVSC

Industry

Scott Corey, Timothy Bail, Spatial Integrated Systems (SIS)

Student

Sandeep Sangha, Virginia Tech

Sakthish Charan Prabakaran, Wayne State University

Project Summary

Project began 2019.

This project aims to develop novel data-driven algorithms to enable the successful deployment of a team of vehicles while addressing uncertainties in the data parameters. In the absence of stochasticity, the problems considered in this proposal are already NP-hard [5, 6] and computationally challenging to solve. In the presence of uncertainties, solving these problems require development of novel computational tools in an interdisciplinary area of research spanning motion planning, optimal control, combinatorial and stochastic optimization.

The main research objective of this proposal is to develop algorithm to handle uncertainty in S-AVPP. This project will provide computationally efficient methods that can find solutions for S-AVPP with guarantees on the deviation of the solutions from the optimum. This will lead to advances in the state-of-the-art approaches for path planning, optimal control, stochastic and combinatorial optimization.

Publications from Prior Work closely related to the proposed project:

S. Faridimehr, S. Venkatachalam, R. Chinnam. “A stochastic programming approach for electric vehicle charging network design,” IEEE Trans. on Intelligent Transportation Systems, 99 (2018): 1-13.
K. Sundar, S. Venkatachalam, S. Rathinam. “Analysis of mixed-integer linear programming formulations for a fuel-constrained multiple vehicle routing problem,” Unmanned Systems, 5.04 (2017): 197-207.
K. Sundar, S. Venkatachalam, S. Rathinam. “Formulations and algorithms for the multiple depot, fuel- constrained, multiple vehicle routing problem,” IEEE American Control Conference (ACC), 2016.
K. Sundar, S. Venkatachalam, S. Manyam. “Path planning for multiple heterogeneous Unmanned Vehicles with uncertain service times,” IEEE Intern. Conf. on Unmanned Aircraft Systems, 2017.
M. Bansal, K.L. Huang, S. Mehrotra. “Decomposition algorithms for two-stage distributionally robust mixed binary programs,” SIAM Journal on Optimization, 28.3: 2360-2383, 2018.
M. Bansal, K.L. Huang, S. Mehrotra. “Tight second stage formulations in two-stage stochastic mixed integer programs,” SIAM Journal on Optimization, 28.1: 788-819, 2018.