Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Path planning using probabilistic cell decomposition
KTH, School of Electrical Engineering (EES).
2005 (English)Licentiate thesis, monograph (Other scientific)
Abstract [en]

The problem of path planning occurs in many areas, such as computational biology, computer animations and computer-aided design. It is of particular importance in the field of robotics. Here, the task is to find a feasible path/trajectory that the robot can follow from a start to a goal configuration. For the basic path planning problem it is often assumed that a perfect model of the world surrounding the robot is known. In industrial robotics, such models are often based on, for example, CAD models. However, in applications of autonomous service robotics less knowledge about the environment is available. Efficient and robust path planning algorithms are here of major importance. To be truly autonomous, a robot should be able to plan all motions on its own. Furthermore, it has to be able to plan and re-plan in real time, which puts hard constraints on the acceptable computation time.

This thesis presents a novel path planning method called Probabilistic Cell Decomposition (PCD). This approach combines the underlying method of cell decomposition with the concept of probabilistic sampling. The cell decomposition is iteratively refined until a collision-free path is found. In each immediate step the current cell decomposition is used to guide probabilistic sampling to important areas.

The basic PCD algorithm can be decomposed into a number of components such as graph search, local planning, cell splitting and probabilistic sampling. For each component different approaches are discussed. The performance of PCD is then tested on a set of benchmark problems. The results are compared to those obtained by one of the most commonly used probabilistic path planning methods, namely Rapidly-exploring Random Trees. It is shown that PCD efficiently solves various kinds of path planning problems.

Planning for autonomous manipulation often involves additional path constraints beyond collision avoidance. This thesis presents an application of PCD to path planning for a mobile manipulator. The robot has to fetch a carton of milk from the refrigerator and place it on the kitchen table. Here, opening the refrigerator involves motion with a pre-specified end-effector path. The results show that planning the different motions for the high-level task takes less time than actually executing them. The whole series of subtasks takes about 1.5 seconds to compute.

Place, publisher, year, edition, pages
Stockholm: KTH , 2005. , x, 73 p.
Keyword [en]
Signalbehandling
Keyword [sv]
Signalbehandling
National Category
Signal Processing
Identifiers
URN: urn:nbn:se:kth:diva-294OAI: oai:DiVA.org:kth-294DiVA: diva2:8678
Presentation
2005-02-10, Kollegiesalen, KTH, 12:00
Supervisors
Note
QC 20101209Available from: 2005-07-11 Created: 2005-07-11 Last updated: 2013-09-05Bibliographically approved

Open Access in DiVA

fulltext(3577 kB)2883 downloads
File information
File name FULLTEXT01.pdfFile size 3577 kBChecksum MD5
16fcc511a63a1d0cee71fafe659704c38522cc0adb5aa61508255f841a970789dab8e9aa
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Lingelbach, Frank
By organisation
School of Electrical Engineering (EES)
Signal Processing

Search outside of DiVA

GoogleGoogle Scholar
Total: 2883 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 3205 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf