Document Type

Article

Publication Date

3-1-1998

Journal or Book Title

Journal of Mechanical Design

Volume

120

Issue

1

First Page

52

Last Page

57

DOI

10.1115/1.2826676

Abstract

Motion planning is a major problem in robotics. The objective is to plan a collision-free path for a robot moving through a workspace populated with obstacles. In this paper, we present a fast and practical algorithm for moving a convex polygonal robot among a set of polygonal obstacles with translations and rotations. The running time is O(c((n + k)N + n log n)), where c is a parameter controlling the precision of the results, n is the total number of obstacle vertices, k is the number of intersections of configuration space obstacles, and N is the number of obstacles, decomposed into convex objects. This work builds upon the slabbing method proposed by Ahrikencheikh et al. [2], which finds an optimal motion for a point among a set of nonoverlapping obstacles. Here, we extend the slabbing method to the motion planning of a convex polygonal robot with translations and rotations, which also allows overlapping configuration space obstacles. This algorithm has been fully implemented and the experimental results show that it is more robust and faster than other approaches.

Comments

This article is from Journal of Mechanical Design 120 (1998): 52–57, doi:10.1115/1.2826676. Posted with permission.

Copyright Owner

ASME

Language

en

File Format

application/pdf

Share

COinS