Carleton University - School of Computer Science Honours Project
Winter 2021
Route Scheduling Coordination for Multiple Agents on Aisle-Graphs
Ryan Kane
SCS Honours Project Image
ABSTRACT
This project aims to create a simulation framework for testing route scheduling algorithms on aisle-graphs for both single and multi-agent cases. The route scheduling algorithms aim to provide a solution to the orienteering problem. This problem is extended to the team orienteering problem when multiple agents are introduced. The orienteering problem has many new real world applications such as robot networks operating to manage inventory in a warehouse, to gather sensor readings in structured lab environments, or perform maintenance along irrigation lines in vineyards. The orienteering problem is known to be NP hard, so approximate algorithms are implemented and analyzed. Other methods for efficiently computing paths and costs on aisle-graphs are also discussed and implemented with the algorithms. Then they are simulated on randomized graphs, and various performance metrics are collected to compare the algorithms. This report shows how adding more agents decrease the collected reward in the Team Orienteering Problem, but because of the advantage of simultaneous execution, more agents also decrease the total time and demonstrate more feasible scalability with the same total budget.