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.

Begreppet konfigurationsrum är ett verktyg som gör det möjligt att motivera rörlighet av ett objekt på ett enhetligt sätt. Problemet med att verifiera icke-existens av möjliga vägar kan betraktas som dualt till vägplanering. Frå-gan vi studerar är om en kropp (en robot, ett fordon eller ett objekt) kan flyttamellan start- och målkonfigurationer utan att kollidera med hinder. Caging ärnett begrepp från robotmanipulation som kan ses som ett speciellt fall av dettaproblem: ett objekt är “caged” när det inte kan komma bort godtyckligt långtfrån sin ursprungliga position. I den här avhandlingen behandlar vi problemen med caging och icke-existens av vägar i olika aspekter. För det första utformar vi en teoretisk ram och verifieringsalgoritmer för caging av tredimensionella partiellt deformerbara objekt med specifika globala geometriska egenskapersom kan beskrivas som smala delar. För det andra formulerar och studerarvi herdingproblemet med hjälp av caging: givet en grupp rörliga agenter ochett team mobila robotar är uppgiften att styra agenterna till en fördefinieradmålregion utan att låta dem fly vid någon tidpunkt. För det tredje föreslår vi en algoritm för effektiv approximering av tre- och sexdimensionella konfigurationsrum av godtyckliga stela objekt. Denna approximation kan senareanvändas för att identifiera caging-konfigurationer såväl som att verifiera ex-istens av vägar mellan givna konfigurationer. Slutligen rapporterar vi vårapreliminära resultat på screening av molekylär caging. Detta projekt byggerpå vårt tidigare arbete med approximering av konfigurationsrum.