Self-Motion Graph in Path Planning Problem with Endeffector

Self-Motion Graph in Path Planning Problem with Endeffector

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


Zhenwang Yao
School of Engineering Science, Simon Fraser University

Inefficiency in Existing Methods and Enhancement Proposed

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.

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.

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.


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


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
More sophisticated planners are proposed, including:
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.

[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

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
Drawback: Depth-first search characteristic
RRT], -Like
Drawback: Slow convergence
RRT], -Connect-Like, RRT], -Greedy-Like, etc.


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).

Success/Failure Success/Failure

RRT], -C
RRT], -G-C

(a) Before

Problem Definition



RRT], -C
RRT], -G-C

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

Comparison in Planning Time (s)

RRT], -C
RRT], -G-C

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

Comparison in Collision Checking (# of calls)

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.

Recently Viewed Presentations

  • Salinas, California -

    Salinas, California -

    CASP History. In March 2008, the Children's Council of Monterey County established the Violence Prevention (VP) Subcommittee. The VP Subcommittee met regularly since April 2008 and focused specifically on ways to reduce gang violence.
  • Light: The Cosmic Messenger - Physics

    Light: The Cosmic Messenger - Physics

    Chapter 5 Light: The Cosmic Messenger Outline Ch 5 Light: The Cosmic Messenger 5.1 Basic Properties of Light and Matter Light: electromagnetic waves Velocity (c = speed of light), wavelength and frequency (colors), energy.
  • Potential Energy - McMaster University

    Potential Energy - McMaster University

    Physics 1D03 - Lecture 34 * Simple Pendulum Gravity is the "restoring force" taking the place of the "spring" in our block/spring system. Instead of x, measure the displacement as the arc length s along the circular path.
  • 1 La prctica de la Adaptacin y Mitigacin

    1 La prctica de la Adaptacin y Mitigacin

    Las ciudades también dan lugar a la producción de emisiones de gases de efecto invernadero fuera de sus fronteras. Las emisiones fuera de la frontera impulsados por las actividades en las ciudades deben por lo tanto también ser incluidos.
  • Fragments - Valencia College

    Fragments - Valencia College

    We placed a comma before the word, trying, because that word is not a proper subject, so that sentence cannot stand on its own. It has to depend on the first independent sentence because it contains a subject, a verb,...
  • Student Orientation to ALEKS Higher Ed Agenda 1

    Student Orientation to ALEKS Higher Ed Agenda 1

    Select the Menu icon in the top, left corner of your home page to access features like your Calendar, Gradebook, Reports, eBook, and more. You can even order a loose-leaf copy of your eBook at a significant discount! The ALEKS...
  • Les Saisons et Le temps - POMS French

    Les Saisons et Le temps - POMS French

    Le Passe Compose. L'été dernier, je suis allée a la plage. J'ai nagé, et j'ai bronzé. Mes amies sont allées avec moi. Elles ont nagé et elles ont bronzé aussi!
  • الخيوط الجراحية

    الخيوط الجراحية

    الخيوط الجراحية د. فهد عبد الله السبيل كلية الزراعة والطب البيطري بعض خواص الخيوط الجراحية المرونة القدرة على الثني الخيوط المرنة تستخدم لربط الوعاء الدموي أو لعمل خياطة مستمرة حرير نايلون كات قت السلك المعدني خواص ...