Semester

Summer

Date of Graduation

2020

Document Type

Thesis

Degree Type

MS

College

Statler College of Engineering and Mineral Resources

Department

Mechanical and Aerospace Engineering

Committee Chair

Yu Gu

Committee Member

Guilherme Peireira

Committee Member

Jason Gross

Abstract

Many future robotic applications such as the operation in large uncertain environment depend on a more autonomous robot. The robotics long term autonomy presents challenges on how to plan and schedule goal locations across multiple days of mission duration. This is an NP-hard problem that is infeasible to solve for an optimal solution due to the large number of vertices to visit. In some cases the robot hardware constraints also adds the requirement to return to a charging station multiple times in a long term mission. The uncertainties in the robot model and environment require the robot planner to account for them beforehand or to adapt and improve its plan during runtime. The problem to be solved in this work is how to plan multiple day routes for a robot where all predefined locations must be visited only a single time and at each route the robot must start and return to the same initial position while respecting the daily maximum operation time constraint. The proposed solution uses problem definitions from the delivery industry and compares various metaheuristic based techniques for planning and scheduling the multiple day routes for a robotic mission. Therefore the problem of planning multiple day routes for a robot is modeled as a time constrained Vehicle Routing Problem where the robot daily plan is limited by how long the robot with a full charge can operate. The costs are modeled as the time a robot takes to move among locations considering robot and environment characteristics. The solution for this method is obtained in a two step process where a greedy initial solution is generated and then a local search is performed using meta-heuristic based methods. A custom time window formulation with respect to the theoretical maximum daily route is presented to add human expert input, priorities or expiration time to the planned routes allowing the planner to be flexible to various robotic applications. This thesis also proposes an intermediary mission control layer, that connects the daily route plan to the robot navigation layer. The goal of the Mission Control is to monitor the robot operation, continuously improve its route and adapt to unexpected events by dropping waypoints according to some defined penalties. This is an iterative process where optimization is performed locally in real time as the robot traverse its goals and offline at the end of each day with the remaining vertices. The performance of the various meta-heuristic and how optimization improves over time are analysed in several robotic route planning and scheduling scenarios. Two robotic simulation environments were built to demonstrate practical application of these methods. An unmanned ground vehicle operated fully autonomously using the presented methods in a simulated underground stone mine environment where the goal is to inspect the pillars for structural failures and a farm environment where the goal is to pollinate flowers with an attached robotic arm. All the optimization methods tested presented significant improvement in the total route costs compared to the initial Path-Cheapest-Arc solution. However the Guided Local Search presented a smaller standard deviation among the methods in most situations. The time-windows allowed for a seamless integration with an expert human input and the mission control layer, forced the robot to operate within the mission constraints by dynamically choosing the routes and the necessity of dropping some of the vertices.

Download

Share

COinS