Abstract
Many modern industries have experienced great benefits from the integration of robotics, especially articulated and mobile robots, into the workspace. As the capabilities and cost efficiency of robots improve, it is increasingly desirable to use robots in service or production chains. One such application which has become a billion-dollar industry in recent years is warehouse management, where mobile robots act as the backbone of the order fulfillment process. However, the question of how to optimally manage the actions of robot fleets in such large and dynamic workspaces remains unsolved.
Review of the literature indicated that there are myriad approaches to generating plans for individual robots, each with different advantages and disadvantages. Without a provably optimal solution available, implementing engineers must therefore make educated guesses and run tests to identify the best solution for their application. This process is clouded by several complexities which arise in real-world applications, including kinematic constraints, the choice of cost function used in optimization, and the random nature of breakdowns in real-world components. While the research largely abstracts away these problems to focus on the underlying optimization of pathfinding, each makes approaching the task of developing and testing algorithms for real systems increasingly complicated. The process is made even more difficult by the knowledge requirements placed on implementing engineers to understand and iterate on the existing research in the first place: the need to understand many programming languages and techniques, the difficulty of ensuring all test cases are treated equally by numerous standalone approaches, and a need for intuition when compensating for edge cases.
To mitigate these burdens and help bridge the gap between simulation and reality, this thesis introduces a strategy which intends to be a generalizable and extensible design pattern for implementation of multi-agent problem simulations. This approach turns out to be very much like a state machine.
Two decoupled multi-agent algorithms, Windowed Hierarchical Cooperative A* and Token Passing with Task Swaps, are presented and implemented using the state machine approach in a completely original computer application named FleetBench.
Using FleetBench, the two algorithms are tested against the same multi-agent scenarios with guarantees regarding similarity in process execution and state data. They compete to produce the best solutions for several representative test cases which provide insight into the advantages of each approach. The resulting data was then analyzed and yielded results similar to the existing research, affirming the accuracy of the implementation.
All test cases were developed and tested rapidly in an intuitive manner using the guided user interface of FleetBench, requiring minimal effort and affirming the practicality of the implementation.
FleetBench is designed to be extensible, accepting additional algorithms and rules. All source code is exposed to the reader and user alongside documentation regarding extension techniques. This extensibility allows FleetBench to grow to suit the needs of the user, gaining value over time as an end-to-end multi-agent testing and development workflow.