Moving a Chair through a Door: A Tutorial on Local Spatial Reasoning in Algorithmic Robotics

Spatial reasoning problems in robotics may be categorised into two types: global and local. A typical problem of the global kind involves determining if a robot can navigate along a specified terrain from one specified (starting) point to another (target) point by means of a suitable path, subject to a variety of constraints. A quintessential example of local spatial reasoning is the determination of whether an object can pass through a specified opening. This paper presents a tutorial on the local spatial reasoning problem of deciding whether a given rigid convex object can pass through a specified convex aperture, and if possible, planning a sequence of motions to accomplish the task, in a computationally efficient manner. The exposition of this material is at the freshman and sophomore undergraduate levels, and is well suited to motivate computer science students in discrete mathematics courses.