Pushing and Pulling: Computing push plans for disk-shaped robots, and dynamic labelings for moving points

Dirk Gerrits

Promotor: prof.dr. M. de Berg (TU/e)
Co-promotor: dr. K. Buchin (TU/e)
Technische Universiteit Eindhoven
Date: 22 August, 2013, 16:00
Thesis: PDF


This thesis covers two classes of problems that seem unrelated at the surface. The first involves path planning, which is a fundamental problem in robotics where the objective is to find a way to move the robot to its destination, without bumping into obstacles along the way. Manipulation path planning is a variant of this problem, in which the robot is to move a passive object to a certain destination, rather than move itself there. This can be effected in various ways, such as carrying the object, rolling it, or even throwing it. We have studied the problem of pushing a disk-shaped object through an environment of polygonal obstacles using a disk-shaped robot. An existing algorithm by Nieuwenhuisen et al. solves this problem, but their method has several deficiencies. Firstly, their method maintains contact between the robot and the object at all times. We show that there are environments in which the only way to get the object to its destination is to occasionally let go of the object, and then resume pushing from a different angle. Secondly, their method uses a great deal of storage space and computation time to preprocess the obstacles. Lastly, no attempt is made to minimize the effort of the pusher robot to achieve the intended object motion. We have developed a new method that fixes these deficiencies: it is efficient in storage and computation time, can compute the shortest possible push plans in case the robot and object can maintain contact at all times, and can still compute a (not necessarily shortest) push plan in the more complicated case where the robot needs to let go of the object on occasion.

The second problem class we study involves map labeling, which is the task of placing textual labels for features on a map such as cities (points), roads (polygonal paths), and lakes (polygons). For readability, labels should not overlap, which means that one should carefully choose which labels to place and where to place them. It takes cartographers considerable time to do this by hand, and for some applications it is not even possible to do by hand ahead of time. In air-traffic control, for example, a set of moving points (airplanes) has to be labeled at all times, each pulling its label along behind it. In interactive maps users may pan, rotate, and/or zoom their view of the map, which may also require relabeling. While there is a vast body of literature on algorithmic methods for the kind of static label placement needed in cartography, far fewer results are known for the kind of dynamic label placement problems inherent in air traffic control and interactive maps. In particular, no study had been made of the theoretical complexity of dynamic labeling. We prove the PSPACE-completeness of a variety of dynamic labeling problems, whose static analogues are NP-complete. In addition, we present a heuristic algorithm—and its experimental evaluation—for labeling a set of moving points. Here the trajectories of the points are assumed to be known beforehand, at least for the immediate future. This has applications in air traffic control (where pilots make their intended course known), and navigation systems (where the driver will presumably follow the computed route). Along the way of developing this dynamic labeling algorithm we identify and fill a gap in the static labeling literature. Labeling a maximal subset of points without overlap is well-studied, but labeling all points while minimizing overlap had not been studied at all. We develop efficient approximation algorithms for this static labeling problem, which are used as a subroutine in our dynamic labeling algorithm.

While static labeling is certainly very different from robot motion planning, when considering dynamic labeling the connection is easily made. Instead of the labels being pulled by their points, we can interpret them as pushing the points along. Labeling moving points then becomes a multi-robot variant of the pushing problem.