Planowanie ruchu bryły sztywnej przez wąskie przejścia w przestrzeni konfiguracji

Michał Nowakiewicz

Abstract

The problem considered in this thesis is that of a 6-DOF rigid body motion planning between two specified positions in presence of known and static obstacles. It has been studied for more than thirty years now. The applications include assembly planning and computer animation. There exist combinatorial methods, which correctly report in a finite amount of time, whether or not a desired motion is possible. These methods have too high complexity to be considered in practice. Instead heuristic methods based on probabilistic sampling of the space of all possible placements of a rigid body have been successfully used to solve many interesting tasks. This work addresses one major problem apparent to these methods, which is a drastic performance decrease in the presence of narrow passages. We present a new sampling based method, whose main ingredient is a heuristic procedure of finding possible locations of narrow passages. This method is the first one to use an approximation of a rigid body with a set of balls for the purpose of motion planning. This approximation allows for a fast estimation of a separation distance or a penetration depth at sampled rigid body positions. The conducted experiments show a huge performance improvement of a new method over classical methods in solving difficult tasks.
Diploma typeDoctor of Philosophy
Author Michał Nowakiewicz (FEIT)
Michał Nowakiewicz,,
- Faculty of Electronics and Information Technology
Title in PolishPlanowanie ruchu bryły sztywnej przez wąskie przejścia w przestrzeni konfiguracji
Languagepl polski
Certifying UnitFaculty of Electronics and Information Technology (FEIT)
Disciplineinformation science / (technology domain) / (technological sciences)
Defense Date29-06-2010
Supervisor Krzysztof Marciniak (FEIT)
Krzysztof Marciniak,,
- Faculty of Electronics and Information Technology

Internal reviewers Jan Zabrodzki (FEIT / IN)
Jan Zabrodzki,,
- The Institute of Computer Science
External reviewers Przemysław Kiciak - [University of Warsaw (UW)]
Przemysław Kiciak,,
-
- Uniwersytet Warszawski
Pages111
Keywords in Englishxxx
Abstract in EnglishThe problem considered in this thesis is that of a 6-DOF rigid body motion planning between two specified positions in presence of known and static obstacles. It has been studied for more than thirty years now. The applications include assembly planning and computer animation. There exist combinatorial methods, which correctly report in a finite amount of time, whether or not a desired motion is possible. These methods have too high complexity to be considered in practice. Instead heuristic methods based on probabilistic sampling of the space of all possible placements of a rigid body have been successfully used to solve many interesting tasks. This work addresses one major problem apparent to these methods, which is a drastic performance decrease in the presence of narrow passages. We present a new sampling based method, whose main ingredient is a heuristic procedure of finding possible locations of narrow passages. This method is the first one to use an approximation of a rigid body with a set of balls for the purpose of motion planning. This approximation allows for a fast estimation of a separation distance or a penetration depth at sampled rigid body positions. The conducted experiments show a huge performance improvement of a new method over classical methods in solving difficult tasks.
Thesis file
Nowakiewicz.pdf 1.91 MB
Citation count*5 (2020-09-18)

Get link to the record

Back
Confirmation
Are you sure?