Circle Packing as a Space Decomposition Method for Robot Path Planning and Coverage

One of the most important tasks for an autonomous robot is figuring out how to move from its current position and orientation to a new position and orientation. Despite significant progress in this area, active research is constantly looking for better ways to plan paths and traverse them. A specific type of path planning called coverage creates a path so that when the robot traverses the path its footprint covers the entire space. Most classical path planning and coverage path planning algorithms have some form of decomposition method for the target space. This work aims to provide a general way to decompose and represent the space so that it can be used both for classical path planning and for coverage. This work accomplishes the aim through using circle packing to tile a space with tangent circles that are the same size as the robot that will traverse the path. These circles are then converted into a planar graph which can be used for path planning and for coverage. The representation created by this decomposition uses less memory than traditional decomposition methods in practice and allows for shorter paths with less curvature to be created in most situations. These statements are shown to hold true for both planning a path between two points in an environment and planning a path to cover the entire environment.