当前位置:   article > 正文

The note of Robot Motion Planning -Chapter 5_robotic motion planning: cell decompositions

robotic motion planning: cell decompositions

原理

  • 将 free space 分解成不重叠的区域集合(cells)。
  • 构造并搜索表示单元间邻接关系的连通图。
  • 搜索成功,得到由Cell组成的序列(channel)。

区域分解应具有以下两个特征:

  • 每个单元尽可能相似,使计算单元中的任何两个configurations的路径简单。
  • 任意两个单元间的邻接性容易测试。容易找到两个共享边界单元的路径。

1 Polygonal Configuration Space

env : c = R 2 c = R_2 c=R2, C-obstacle region CB forms a polygonal region in C.
free space C f r e e C_{free} Cfree is bounded.
在这里插入图片描述

**DEFINITION 1: A convex polygonal decomposition K,**of C f r e e C_{free} Cfree is
a finite collection of convex polygons, called cells, such that the interiors of any two cells do not intersect and the union of all the cells is equal to c l ( C f r e e ) cl(C_{free}) cl(Cfree). Two cells K and K’ in K are adjacent if only if K n K’ is a line segment of non-zero length.

DEFINITION 2: The connectivity graph G associated with a convex polygonal decomposition k k k of C f r e e C_{free} Cfree is the non-directed graph specified as follows:

  • G’s nodes are the cells in K K K.
  • Two nodes in G are connected by a link if and only if the corresponding cells are adjacent.

在这里插入图片描述

The exact cell decomposition algorithm for planning a free path
connecting the two configurations is the following:

  1. Generate a convex polygonal decomposition k k k of C f r e e C_{free} Cfree.
  2. Construct the connectivity graph G associated with k k k.
  3. Search G for a sequence of adjacent cells between q i n i t q_{init} qinit and
    q g o a l q_{goal} qgoal·
  4. If the search terminates successfully, return the generated sequence of cells; otherwise, return failure.
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/码创造者/article/detail/879211
推荐阅读
相关标签
  

闽ICP备14008679号