Path-Connectivity of the Free Space : Caging and Path Existence

Sammanfattning: The notion of configuration space is a tool that allows to reason aboutan object’s mobility in a unified manner. The problem of verifying path non-existence can be considered as dual to path planning. The question here iswhether a body (a robot, a vehicle, or an object) can move between start andgoal configurations without colliding with obstacles. Caging is a notion fromrobotic manipulation that can be seen as a special case of this problem: anobject is caged when it cannot escape arbitrarily far from its initial position.In this thesis, we address the problems of caging and path non-existence indifferent settings. Firstly, we design a theoretical framework and verificationalgorithms for caging of three-dimensional partially-deformable objects withspecific global geometric features that can be described as narrow parts. Sec-ondly, we formulate and address the problem of herding by caging: given agroup of moving agents and a team of mobile robots, the task is to guide theagents to a predefined goal region without letting them escape at any mo-ment of time. Thirdly, we propose an algorithm for efficient approximationof three- and six-dimensional configuration spaces of arbitrary rigid objects.This approximation can be later used to identify caging configurations as wellas to verify path existence between given configurations. Finally, we reportour preliminary results on molecular caging screening. This project buildsupon our previous work on configuration space approximation.