Data-driven task allocation for multi-robot deliveries

In this thesis, we present a distributed task allocation system for a team of robots serving queues of tasks in an environment. We consider how historical information about such a system's performance could be used to improve future allocations. Our model is representative of a multi-robot mail delivery service, in which teams of robots would have to cooperate to pick up and deliver packages in an environment. We provide a framework for task allocation, planning, and control of the system and analyze task switching as a method for improving a task allocation as the system is running. We first treat a system where robots exchange tasks as they encounter each other in the environment. We consider both cases where the number of robots matches the number of task queues being served and where it does not. Most importantly, for situations where an optimal task switching policy would be too computationally expensive, we provide heuristics that nonetheless guarantee task completion. Our simulations show that our heuristics also generally lower the costs of task completion. We incorporate historical data about system performance by looking at a spatial allocation of tasks to robots in the system. We propose an algorithm for partitioning the environment into regions of equal workload for the robots. In order to overcome communication constraints, we introduce hubs, locations where robots can pass tasks to each other. We simulate the system with this additional infrastructure and compare its performance to that without hubs. We find that hubs can significantly improve performance when the task queues themselves follow some spatial structure.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2013

Author dc:creator

• Sung, Cynthia Rueyi

Advisor dc:contributor.advisor

• Daniela Rus.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/84717

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/84717