The basic problem is to find a minimum distance path for an UAV that visits a given set of survilleance points in the presence of yaw rate constraints of the UAV. This problem has two coupled sub problems: 1) the combinatorial subproblem that requires finding a sequence of points for a UAV to visit, 2) the motion planning subproblem that requires finding a path that satisfies the yaw rate constraints of the UAV. One can also think of the generalization of the single vehicle problem extended to multiple vehicles. I have developed approximation algorithms and lower bounds for these combinatorial motion planning problems in the following papers.
Please refer to the following publication to see the recent work.
Journal Publications:
M. Gupta, S. Rathinam and S. Darbha, Lower Bounds for a Multiple Vehicle Routing Problem with Motion Constraints, ASME Journal on Dynamic Systems, Measurement and Control, Revised version submitted in Aug 2014. (pdf)
M. Gupta, S. Rathinam and S. Darbha, Lower Bounds for a Vehicle Routing Problem with Motion Constraints, International Journal of Robotics and Automation, Accepted in June 2014. (pdf)
S. Rathinam, R. Sengupta and D. Swaroop. A Resource Allocation Algorithm for Multi Vehicle Systems with Non-Holonomic Constraints. IEEE Transactions on Automation Science and Engineering, Volume 4, No. 1, January 2007. (pdf)
Book Chapters:
S. Rathinam, R. Sengupta and S. Darbha. Path Planning for a Collection of Vehicles with Yaw Rate Constraints. Springer Series Lecture Notes in Economics and Mathematical Systems, vol 588, January 2007.
S. Rathinam and R. Sengupta, Routing Problems involving UAVs, Innovations in Intelligent Machines: Theory and Applications, Springer Series, June 2007.
Conference Publications:
M. Gupta., S. Rathinam and S. Darbha, Computation of Lower bounds for a Multiple Depot, Multiple Vehicle Routing Problem With Motion Constraints, IEEE Conference on Decision and Control, Firenze, Italy, December 2013.
M. Gupta.., S. Rathinam, S. Darbha, and K. J. Obermeyer. Computation of a Lower Bound for a Vehicle Routing Problem with Motion Constraints. ASME Dynamic Systems and Control Conference, Ft. Lauderdale, FL, USA, October 2012.
S. Yadlapalli.., W. A. Malik.., S. Darbha and S. Rathinam. A Lagrangian-Based Algorithm for a Combinatorial Motion Planning Problem with Precedence Constraints. Springer Series Lecture Notes in Control and Information Sciences, 2007.
S. Rathinam, W. Malik.., S. Yadlapalli.. and S. Darbha. Algorithms for the Dubins Traveling Salesman Problem. Conference on Cooperative Control and Optimization, 2008, Florida.
S. Yadlapalli.., W. A. Malik.., S. Rathinam, and S. Darbha. A Lagrangian-Based Algorithm for a Combinatorial Motion Planning Problem. IEEE Conference on Decision and Control, 2007.
W. Malik.., S. Rathinam, S. Darbha and D. Je.coat. Combinatorial Motion Planning for Multiple Vehicle Systems. IEEE Conference on Decision and Control, December 2006, San Diego.
W. Malik.., S. Rathinam, S. Darbha and D. Jeff.coat. Combinatorial Motion Planning for a Collection of Reeds-Shepp Vehicles. Informs Annual Meeting, 2005.
S. Rathinam and R. Sengupta. Lower and Upper bounds for a Multiple Depot Routing Problem. IEEE Conference on Decision and Control, December 2006, San Diego.