Algorithms for Rectangular Robot Motion Planning

Agarwal, Pankaj Kumar

Steiger, Alexander John

2023-10-03T13:35:42Z

2023

Computer Science

With the proliferation of robot deployment in large-scale operations, such as warehouse management and manufacturing, there is an increasing need for multi-robot motion planning solutions. The basic multi-robot motion planning problem is to decide whether robots can translate from given start positions to given target positions without colliding with each other or any obstacles in the environment on their way, and if so, to compute such collision-free paths. Together, such paths compose a collision-free motion plan.

In practice, there are other qualities to consider besides being collision-free, such as the lengths of the paths, the overall time for all robots to follow their paths, and robustness. We explore this problem space, called optimal multi-robot motion planning. In light of previous hardness results, we focus on instances where the robot(s) and obstacles are assumed to have simple but realistic geometric properties with the goal of describing algorithms that are provably efficient and/or compute high-quality solutions. A frequent aspect of our work is to suppose that the input objects (robots and/or obstacles) are rectangular objects with bounded aspect ratio; that is, the side lengths of the objects are similar in proportion to each other.

Motivated by applications to motion planning and others,we explore the problem of computing and decomposing the common exterior of a set of n 3D axis-aligned cubes. We first present an algorithm to compute the common exterior, whose runtime is nearly optimal and output-sensitive in the sense that the running time depends linearly on the complexity of the common exterior, k, and not the worst-case complexity, Θ(n^2), by exploiting the geometry of the cubes.

Second, we describe an algorithm to further process the common exterior of n axis-aligned cubes into a partition composed of simple regions, specifically axis-aligned boxes. Our partition has size near-linear in the complexity of the union, k, and Ω(k) is a lower bound on the size of any partition.We also describe a simpler algorithm to partition the common exterior of n axis-aligned boxes of arbitrary sizes into O(n^(3/2) + k) axis-aligned boxes, which is optimal in the sense that min{n^(3/2),k} is a worst-case lower bound. In the context of motion planning, our algorithms can be used to compute a small partition of the free space for a box-shaped robot amid obstacles approximated by a set of boxes.

Lastly, we consider a special case of the min-sum motion planning problem, which falls under the umbrella of optimal motion planning. The goal is to compute a motion plan that minimizes the total length of the paths to be followed by the robots. This problem is well-studied for a single robot and polynomial-time algorithms to compute the optimal motion plan are known.However, we are not aware of any polynomial time algorithm for this problem, nor do we know whether the problem is NP-hard. We consider instances of this problem for congruent square robots amid polygonal obstacles in the plane. Our result is a fully polynomial-time approximation scheme (FPTAS) for these instances, which is the first (1+ε)-approximation algorithm for an optimal motion planning problem involving two robots moving in a polygonal environment.

https://hdl.handle.net/10161/29129

Computer science

Algorithms for Rectangular Robot Motion Planning

Dissertation

5

2024-03-14T00:00:00Z