Robot Motion Planning

Given a set of obstacles $P_1,\cdots,P_k$ , and a polygonal robot $R$ with starting configuration $s$ and target configuration $t$ . Find a path for the robot from $s$ to $t$ if possible.

机器人路径规划问题，首先应该先解决：存不存在这样一条路径的问题。

Reference point

define a reference point $p$ of the robot and define position of the vertices of $R$ w.r.t. $p$ .

Suppose our robot can move by translating

$R(x,y)$ : position of the robot when the reference point is at $(x,y)$ .

Suppose our robot can move by translating:

$R(x,y,\alpha)$ : position of the robot when the reference point is at $(x,y)$ and the robot has orientation $\alpha$ .

We represent the robot by a point in the parameter space (configuration space) $\mathbb R^2\times[0,360)$

先只考虑机器人只能平移，不能旋转。

partition the configuration space in free space and forbidden space

$p$ in forbidden space $\Lrarr R(p)$ intersects an obstacle.

$R$ can move from $s$ to $t\Lrarr$ there is a path from $s$ to $t$ in the free space.

对于机器人上的一个参考点，在图上都有一个 free space 图。如果 free space 联通起始点，那么就存在一个路径使得机器人可以从起点移动到终点。

if $R$ is a point then configuration space = work space.

Finding a path in the Configuration Space

如果存在路径，那么就找出这样一条路径

given a configuration space $P_1,\cdots,P_k$ of complexity $n$ find a path from $s$ to $t$ if possible.

idea: construct a trapezoidal decomposition of the free space.

思路：将 free space 用竖线进行梯形分解。

construct a road map $G=(V,E)$

$V$ : set of all centers of all trapezoids $\Delta$ and all midpoints of all vertical segments $s$ .

梯形的中位线中点+所有梯形顶边和底边线段的中点

$(\Delta,s)\in E\Lrarr s$ is a vertical segment bounding $\Delta$ .

add $s$ and $t$ to $G$ and connect them to the trapezoids containing them.

Run a BFS in the road map to find a path from $s$ to $t$ .

Theorem

we can compute a path from $s$ to $t$ in $\mathcal O(n\log n)$ expected time.

如何搞定 free space 的计算问题呢？使用闵可夫斯基和解决！

Minkowski Sums

Let $P$ and $R$ be two sets in $\mathbb R^2$

$P\oplus R=\{p+r|p\in R\and r\in R\}$ is the Minkowski sum of $P$ and $R$ .

where $p+r=\{p_x+r_x,p_y+r_y\}$

observation: let $Q=P\oplus R$ , an extreme point on $Q$ in direction $d$ is the sum of extreme points in direction $d$ on $P$ and $R$ .

Theorem

Let $P$ and $R$ be convex polygons with $n$ and $m$ edges, then $Q=P\oplus R$ is a convex polygon and has at most $m+n$ edges.
Let $P$ and $R$ be convex polygons with $n$ and $m$ edges, then $Q=P\oplus R$ can e computed in $\mathcal O(m+n)$ time.

Question: What if $P$ and $R$ are not convex?

Pseudo-discs

a pair $P$ and $R$ are pseudo-discs

the boundaries of $P$ and $R$ intersect in at most two points.

i.e.,

\partial P\cap int(R)\text{ is connected and}\\ \partial R\cap int(P)\text{ is connected.}

observation: A pair of polygonal pseudo-discs $P$ and $R$ defines at most two boundary crossing

Theorem

Let $\mathcal S$ be a collection of convex polygonal pseudo-discs with a total of $n$ edges. the total complexity of their union is at most $2n$ .

pseudo-disk vertices
intersection points

Charge every pseudo-disk vertex to itself.

For an intersection point $q=e\cap f$ , by observation: either

$e$ has no other boundary crossing with $\part R$ .
$f$ has no other boundary crossing with $\part P$ , or both

Let $e$ be the edge without other boundary crossings, and let $v$ be the endpoint of $e$ in $R$ .

Charge $q$ to $v$ .

Claim: Every vertex $v$ (of a pseudo-disk $P$ ) is charged at most twice.

Case 1: $v$ not in any other pseudo-disk ∴ $v$ is a green vertex and is charged only by itself.
Case 2: $v,v\in R$ lies in the interior of the union.
Traverse $e=\overline{vw}$ . There is only one point $q$ on the boundary of the union on $e$ that charges to $v$ .
Same for the other edge $\overline{vu}$
Case 3: $v,v\in\part R$ lies on the boundary of the union. As in case 2 $v$ is charged only by its incident edges $e$ and $f$ and by $v$ itself
$v$ can not be charged by both its incident edges at the same time.

Let $\mathcal S$ be a collection of pseudo-discs with a total of $n$ edges. The total complexity of their union is at most $O(n)$ .

Observation: Let $P$ and $R$ be convex polygons with disjoint interiors, let $d_1$ and $d_2$ be directions where $P$ is more extreme than $R$ .

Then either

$P$ is more extreme in all directions in $[d_1,d_2]$ , or
$P$ is more extreme in all directions in $[d_2,d_1]$ .

Let $P$ and $Q$ be two convex polygons with disjoint interiors, and let $R$ be another convex polygon. Then $P\oplus R$ and $Q\oplus R$ are pseudo-discs.

To show: $\part P\oplus R\cap int(Q\oplus R)$ is connected.

Proof by contradiction. Assume $\part P\oplus R\cap int(Q\oplus R)$ is not connected.

By observation, an extreme point on $P\oplus R$ corresponds to a extreme point on $P$ . Same for $Q$ .

$\Rarr P$ more extreme on $d_p$ and $d_q$ than $Q$

$\Rarr Q$ more extreme on $d_s$ and $d_r$ than $P$

What if $P$ is not convex?

observation: for any set $P,Q,R$
$R\oplus(P\cup Q)=(R\oplus P)\cup(R\oplus Q)$
Triangulate $P$
$\Rarr$ this produces a collection of disjoint convex polygons, so the collection of Minkowski sums is a collection of pseudo-disks.

Let $P$ be a polygon with $n$ vertices, and let $R$ be a convex polygon with $m$ vertices. Then complexity of $P\oplus R$ is $\Theta(mn)$ .

What if $P$ and $R$ are both not convex?

Triangulate both $P$ and $R$ . This gives a collection of $O(mn)$ triangles.

Let $P$ be a polygon with $n$ vertices, and let $R$ be a convex polygon with $m$ vertices, The complexity of $P\oplus R$ is $\Theta(n^2m^2)$ .

Let $P$ be a polygon with $n$ vertices, and let $R$ be a convex polygon with $m=O(1)$ vertices, we can compute $P\oplus R$ in $\mathcal O(n^2\log n)$ time.

好麻啊这一段

Minkowski Sum & Robot Motion Planning

Let $-p=(-p_x,-p_y)$ and $-\mathcal S=\{-p|p\in\mathcal S\}$

Lemma. Let $P$ be an obstacle and let $R$ be a planar, translating robot. A point $q$ in the configuration space is forbidden iff $q\in P\oplus(-R(0,0))$ .

In direction:

suppose $q\in P\cap R(x,y)$

q\in R(x,y)\Rarr q-(x,y)\in R(0,0)\\ -q+(x,y)\in-R(0,0)\\ q\in P\Rarr(x,y)\in P\oplus-(R(0,0))

Only if direction: similar.

Question: How do we compute the free/forbidden space in the configuration space?

Forbidden space $=\cup_iP_i\oplus-(R(0,0))$

So if $R$ is convex and has constant complexity, and the input polygons have a total $n$ vertices we can compute the forbidden space in $O(n\log^2n)$ time.

Shortest Paths

Given a set of obstacles $P_1,\cdots,P_h$ , a starting point $s$ and target point $t$ . Find a shortest path from $s$ to $t$ ,

Lemma A shortest pat between $s$ and $t$ among a st of disjoint obstacles $P_1,\cdots,P_h$ is a polygonal path whose inner vertices are vertices of $P_1,\cdots,P_h$ .

Question: how do we compute a shortest path between $s$ and $t$ ?

idea: Construct a graph $G=(V,E,w)$ with edge length s.t. for $(u,v)\in E$ the edge corresponds to the distance between $u$ and $v$ .
$V=$ the set of obstacle vertex $v$ and $s$ and $t$
$(u,v)\in E\Lrarr u$ and $v$ can see each other
$w(u,v)=||uv||$