Self-Motion Graph in Path Planning Problem with Endeffector Path Specified

Robotics

Labortrary

Zhenwang Yao

School of Engineering Science, Simon Fraser University

Inefficiency in Existing Methods and Enhancement Proposed

Abstract

Redundant robots have good dexterity in avoiding

obstacles when performing tasks. We propose an

enhanced probabilistic method to solve the problem of

path planning along a specified end-effector path.

Introducing a data structure named Self-Motion Graph,

we allow robot self-motion along the end-effect path.

Computer simulations show that this enhancement

improves performance in some simulated cases.

Inefficiency:

As shown on the left, with current planners and the same parameters, the two scenes attempt to find a path

starting with different configurations for the first pose. T], he experimental result demonstrates that a bad

configuration may result in failure to find a path.

Explanation:

In the current planners, no self-motion is allowed, therefore the number of configurations in the final found joint

path is limited to the number of poses in the end-effector path. At the same time two consecutive configurations

should be close enough, such that the end-effector does not move off the specified path. T], hese two constraints

restrict the robot to move out of a bad configuration by a limited number of small movements, which may be

difficult in some cases.

(a) Start with a bad conf.

Current

Planners

Proposed enhancement:

T], o allow the self-motion.

What is self-motion:

Self-motion is a movement that does not affect the end-effector pose (position and orientation). Mathematically,

self-motion is in the null-space of the Jacobian matrices. Self-motion can be used to satisfy additional

constraints including obstacle avoidance, joint limit avoidance, and singularity avoidance. In our enhancement,

we explore self-motion in a probabilistic fashion.

Fig 1. T], he problem.

Related Work

8/12

15/5

19/1

Conclusion

By introducing the Self-Motion Graph, an enhancement

is proposed based on current probabilistic planners for

path planning problem with end-effector path specified.

T], o explore robot self-motion, we adopt configuration

generation techniques for closed-chain robots.

Computer simulations prove that this enhancement

indeed improves the performance, in terms of finding a

collision-free path.

Incorporation into current planners:

In the tree-type data structure used by the current planners,

each level of the tree corresponds to a pose along the endeffector path. Self-motion is incorporated into the planners by

further expanding a node in the tree into an equivalent group

of nodes corresponding to the same pose, which is

represented by a connected graph, called the Self-Motion

Graph (SMG).

(b) After

Self-Motion Graph Exploration:

T], o reduce the computation to build and search the explored

tree, we only create SMGs when required. Only for the poses

where the robot has difficulty extending further the SMGs are

propagated; for the poses where the planners can extend to

the next pose within a fixed number of retries, simple nodes

are retained.

SMG-Greedy, the Greedy planner proposed in [3] enhanced

by SMG, has the following procedure:

1. Explore the path as the original Greedy planner.

2. Create a new SMG for the pose where the planner fails

to extend further.

3. Repeatedly explore the SMG until a feasible

configuration is found to achieve the next pose, or the

size of the SMG reaches the limit.

T], he data structure used to store the generated configurations

now is different. As shown on the left, (a) is the data structure

in the original Greedy planner, and (b) is the data structure in

SMG-Greedy.

More sophisticated planners are proposed, including:

1. SMG-RRT-C;

2. SMG-RRT-C2;

for more details, please refer to [7].

Future Work

T], he future work will focus on path smoothing. T], he path

found by probabilistic methods normally has some

jerky movements, and path smoothing is to reduce the

jerky movements and optimize the path for later

execution stage.

Reference

[1] A. Maciejewski and C. Klein. Obstacle avoidance for

kinematically redundant manipulators in dynamically varying

environments. International Journal of Robotics Research,

4:109117, 1985.

T], he approaches for this problem:

1. On-line, Local

Jacobian-based methods [1]

Drawback: Local minimum issues

2. Off-line, Global

Extension from Jacobian-based methods [2]

Drawback: High computation

Probabilistic methods [3]

Of our main interest

[2] S. Seereeram and J.T], . Wen. A global approach to path

planning for redundant manipulators. IEEE Transactions on

Robotics and Automation, 11:152160, 1995.

Experimental Results

(a)

Probabilistic Methods

T], he basic idea is to establishe connections among

semi-randomly generated configurations for the

sequential sampling poses:

Configuration Generation: (semi-random) techniques

for closed-chain robots

Active-passive link decomposition [4]

Random loop generator [5]

Planning Strategies

Greedy

Drawback: Depth-first search characteristic

RRT], -Like

Drawback: Slow convergence

Combinations

RRT], -Connect-Like, RRT], -Greedy-Like, etc.

0/20

0/20

0/20

Data Structure and Implementation

Self-Motion Graph:

As shown in the figure above, given an end-effector path

in workspace,

xg(t); t[0; T], ],

and a start robot configuration q0, determine an entire

joint space path q(t), such that

F(q(t)) = xg(t);

t[0; T], ],

where F(q) is the robot forward kinematics function.

(b) Start with a good conf.

T], he problem, the path planning problem with endeffector path specified, has wide applications, such as

cutting, painting, inspection, etc. SMGs help in

applications where time requirement along the endeffector path is loose, like inspection robots. On the

other hand, some applications may not benefit from

this enhancement. For example, in spray painting

applications, a constant end-effector velocity is

required along the end-effector path, and self-motion

generates an inconstant end-effector velocity (thereby

uneven paint deposition may result).

(a)

(b)

Success/Failure Success/Failure

Greedy

RRT], -C

RRT], -G-C

(a) Before

Problem Definition

Applications

(b)

Planners

Greedy

RRT], -C

RRT], -G-C

SMG-Greedy

SMG-RRT], -C

SMG-RRT], -C2

Case (a) Case (b) Case (c)

43.5

19.4

29.9

43.6

3.8

18.1

11.6

5.7

7.6

8.7

2.5

6.2

9.4

3.7

6.8

11.1

3.0

13.0

Comparison in Planning Time (s)

(c)

Planners

Greedy

RRT], -C

RRT], -G-C

SMG-Greedy

SMG-RRT], -C

SMG-RRT], -C2

Case (a) Case (b) Case (c)

24457

99366

69552

6038

80573

35818

8659

21380

14242

3528

16007

11061

5462

15330

10812

3852

11210

10818

Comparison in Collision Checking (# of calls)

Note:

1. T], he running time is measured on a Pentium-4 2.0G PC.

2. T], he experiments were done with our in-house developed software library MPK, the Motion Planning Kernel [6].

3. T], he first three planners are the planners in [3], and the last three planners are enhanced by Self-Motion Graph.

Copyright Zhenwang Yao, 2004

[3] G. Oriolo, M. Ottavi, and M. Vendittelli. Probabilistic

motion planning for redundant robots along given endeffector paths. In IEEE/RSJ International Conference on

Intelligent Robots and Systems, pages

16571662, 2002.

[4] L. Han and N. Amato. A kinematics-based probabilistic

roadmap method for closed kinematic chains. In B. Donald,

K. Lynch, and D. Rus, editors, Workshop on Algorithmic

Foundations of Robotics, pages 233246, March 2000.

[5] J. Cortes, T], . Simeon, and J.P. Laumond. A random loop

generator for planning the motions of closed kinematic chains

with PRM methods. In IEEE International Conference on

Robotics and Automation, pages 21412146, 2002.

[6] I. Gipson, K. Gupta, and M. Greenspan. MPK: An open

extensible motion planning kernel. Journal of Robotic

Systems, 18(8):433443, Aug. 2001.

[7]. Z. Yao. Self-motion graph in path planning problems with

end-effector path specified. In ENSC-894 Course

Transactions, Simon Fraser University, Summer, 2005.