
We consider motion planning under the compliant motion model, in which a robot directed to walk into a wall may slide along it. We examine several variants of compliant motion planning for a point robot inside a simple polygon with n sides, where the goal is a fixed vertex or edge. For the case in which the robot moves with perfect control, we build a data structure that lets us in O(log n) time determine the range of directions in which the robot can move from a query point to the goal in a single step. This structure lets us solve a variety of other problems: we can find a similar query data structure for multi-step paths; we can solve single-step problems allowing uncertainty in control and position sensing; and we can explicitly compute the set of all points that can reach the goal in a single step, even allowing uncertainty in control. Our algorithms run in O(n log n) time and linear space; they use a novel method for maintaining convex hulls of simple paths that may be of independent interest.
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 17 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
