Handling Autonomous Robot Scheduling as an Optimization Problem

Abstract

This dissertation investigates the possibility to model the behavior of an agent solving a complex robotic scheduling task, mission 7a of the International Aerial Robotics Competition, as an optimization problem known as the Time-Dependent Orienteering Problem with Time Windows. The robot environment is stochastic and dynamic, and the agent has to make decisions in real time, with little to no possibility for preprocessing. Solution techniques for the problem model and specializations of the problem have been investigated, along with the swarm algorithms Ant Colony Optimization Algorithm and Intelligent Water Drops Algorithm.

The swarm algorithms were implemented and applied to the problem model. The resulting system was used by a controller to solve the mission in a simulator, where the performance was evaluated by comparing the scheduler with a simple greedy controller.

Experiments show that the Intelligent Water Drops Algorithm and Ant Colony Optimization Algorithm were able to find solutions of adequate quality. Modeling the International Aerial Robotics Competition as a Time-Dependent Orienteering Problem with Time Windows showed great promise, and the scheduler performed better than the greedy controller.

The Ant Colony Optimization Algorithm had better performance than Intelligent Water Drops Algorithm in both solving the Time-Dependent Orienteering Problem with Time Windows and the mission. The Intelligent Water Drops Algorithm showed difficulties with completing plans when used in the controller because of large solution deviations. The performance of the system in the real world is uncertain, and partial observability may need to be addressed by Ascend NTNU before the competition.