Motion Planning with Discrete Geodesics

No Thumbnail Available

Date

2021-12-09

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Several civil and military applications such as surveillance and reconnaissance require unmanned vehicles to visit targets while being optimized for travel time, fuel, and other communication and kinematic constraints. Unmanned vehicles could also have other limitations set by the size, the design, and the environment. This thesis considers discrete path planning problems for unmanned vehicles. The shortest continuous path for a constant speed vehicle from any arbitrary initial location and orientation to any arbitrary final location and orientation in the absence of obstacles takes the form of a Dubin’s path. While these paths are continuous and smooth, this thesis explores the case when the paths could be discrete instead. Dubin’s path is always one of the six kinds which could be an LRL. RLR, RSR, LSL, RSL, LSR; were L and R, are left and right turn arc segments respectively, and S is a straight-line segment. This thesis is concerned with similar paths except that the L and R, are left and right turn polygonal arc segments instead. Our work will prove that the discrete paths are shorter than their continuous counterparts. Moreover, the discrete paths are a more general form since they could generate the same results as the continuous counterpart when the polygonal arc chord length limits to zero. This is because a circular arc could be imagined as a polygonal arc with infinite edges. These paths are particularly relevant when we consider environments to travel with limited communication abilities. In GPS denied or GPS limited environments, performing discrete straight segment maneuvers are more reliable than traversing through circular arc segments especially since we do not have GPS feedback. Every vertex of the polygonal path could be imagined as ‘position’ (or ‘time’ when traveling in a constant speed) where the GPS location could be pinged for instead of relying on GPS feedback for the entire tour. The thesis characterizes the Discrete Geodesics with both non-inflection and inflection segments and presents explores algorithms. The work explores a more generic and beneficial version of the Dubin’s paths extended to study traveling salesmen problems.

Description

Keywords

Geodesic, Travelling Salesman Problem, TSP, UAV, Dubin, Shortest Path, Rotary Steerable Systems, RSS

Citation