The increasing availability of low-cost, compliant and human-friendly manipulators allows robots, such as Rethink Robotics' Baxter, to be placed in close proximity to human workers. Unlike traditional automation systems, which needed to be kept in cages, these compliant robots can share a common workspace with human workers. A clear benefit of this close proximity is the opportunity for cooperation between a human worker and an assistive robot.
This project focuses on Multi-Robot Path Planning, with the goal of providing a complete and tractable solution to such instances. The current work considers an abstraction of the traditional multi-robot path planning problem that is abstracted as computing non-colliding paths for multiple agents between their start and goal locations on a graph. Such a formulation is known to be NP-complete, indicating that a naive search to solve the problem will have exponential complexity in the number of robots.
Probabilistic roadmap planners utilize an offline phase to build up information about the configuration space (C-space) and solve many practical motion planning problems. Traditionally, many of these planners focus on feasibility and may return paths of low quality; considerably different from the optimal ones, where path quality can be measured in terms of length, clearance, or smoothness. Smoothing can be used to improve some of these measures and algorithms exist that produce roadmaps with paths that are deformable to optimal ones. Hybridization graphs combine multiple solutions into a higher quality one that uses the best portions of each input path. These techniques, however, can be expensive for the online resolution of a query, especially when multiple queries must be answered.