75
Thus
the
first
subconstraint
leads
directly
to
the
PPP.
Find
an
image
set
n
such
that x
nos
=
0.
(PPP)
Now,
consider
the
second
subconstraint
x(t)
n
0-(t) =
0.
We
control
two
factors
to
satisfy
this
sub-
constraint :
the
image
sets
and
the
correspondence
Hz(’).
T -
x.
Assume
that
we
choose
as
that
satisfies
the
first
subconstraint.
The
second
subconstraint
leads
to
the
velocity
planning
problem.
Given
the
image
set
7r,
find
a
correspondence
To
summarize,
we
have
formalized
the
TPP =>
PPP
+
VPP
decomposition.
This
implies
that
the
problem
of
planning
the
trajectory
of
a
point
robot
among
obstacles
is
decomposed
into
two
subproblems:
planning
the
path
so
that
a
collision
with
static
obsta-
cles
is
avoided
and
planning
the
velocity
along
this
path
so
that
a
collision
with
moving
obstacles
is
avoided.
3.
Solving
the
PPP
and
the
VPP
With
the
TPP ~
PPP
+
VPP
decomposition
estab-
lished,
we
next
give
an
algorithm
for
solving
the
VPP.
Since
this
algorithm
presumes
a
path,
we
will
first
briefly
review
current
approaches
to
the
PPP.
3.1.
THE
PPP-DETERMINING
A
PATH
The
aim
of
path
planning
is
to
come
up
with
an
ex-
plicit
representation
of
the
collision-free
paths
that
a
robot
may
take.
Geometrically,
we
may
view
it
in
two
complementary
ways:
planning
the
path
so
that
it
avoids
the
obstacles
or
planning
the
path
so
that
it
lies
in
the
free
space,
i.e.,
physical
space
minus
the
obsta-
cles.
We
will
give
an
algorithm
from
each
approach.
3.1.1.
Ygraph Algarit~n2
In
a
two-dimensional
polygonal
world,
a
necessary
condition
for
a
minimum
length
path
is
for
it
to
be
composed
of
straight
line
segments
connecting
a
subset
Fig.
1.
The
Ygraph
algo-
rithm to
solve
the
two-di-
mensional
PPP.
The
shaded
polygons
are
obstacles.
The
shortest
collision-free
path
from
I
to
F
(shown
in
bold
lines)
is
composed
of straight
line
segments
joining
vertices
of the
obstacles.
of
the
vertices
of
the
polygonal
obstacles
(Wangdahl,
Pollock,
and
Woodward
1974;
Lozano-Perez
and
Wesley
1979).
For
an
intuitive
proof,
see
the
MinPath
Theorem
in
Appendix
II.
A
two-dimensional
PPP
is
solved
as
follows.
Consider
the
graph
YG
with
the
set
of
nodes
N
=
(I,
F)
U
V,
where
I
corresponds
to
the
initial
position
and
F
to
the
final
position.
V is
the
set
of
vertices
of
the
polygonal
obstacles.
Construct
the
edge
set
E
of
all
the
edges
(ni,
nj)
such
that
the
straight
line
connecting
node n,
to
node nj
does
not
intersect
any
of
the
obstacles.
This
graph
VG(N,
E)
is
called
the
Vgraph
and
the
optimal
(shortest)
collision-free
path
from
I
to
F
is
given
by
the
minimum
cost
(graph)
path
from node
I
to
node
F.
The
cost
of
an
edge
is
given
by
the
Euclidean
metric.
The
Vgraph
Algorithm
is
illus-
trated
in
Fig.
1.
A
version
of
this
algorithm
has
been
used
by
Moro-
vac
( 1980}
to
plan
paths
for
a
robot
among
circular
obstacles
in
a
plane.
The
algorithm
can
be
generalized
to
the
3-D
case;
however,
it
does
not
yield
shortest
paths.
One
approach
is
to
introduce
additional
vertices
along
the
edges
of
the
obstacles
(Lozano-Perez
and
Wesley
1979).
Still,
nonexponential
algorithms
are
not
currently
known
for
finding
shortest
paths
among
3-D
polyhedral
obstacles.*
----
* We
thank
one
of
the
referees
for
pointing
this
out.
剩余17页未读，继续阅读
呆呆美要暴富
- 粉丝: 36
- 资源: 339
我的内容管理
展开
最新资源
- 新型矿用本安直流稳压电源设计：双重保护电路
- 煤矿掘进工作面安全因素研究：结构方程模型
- 利用同位素位移探测原子内部新型力
- 钻锚机钻臂动力学仿真分析与优化
- 钻孔成像技术在巷道松动圈检测与支护设计中的应用
- 极化与非极化ep碰撞中J/ψ的Sivers与cos2φ效应：理论分析与COMPASS验证
- 新疆矿区1200m深孔钻探关键技术与实践
- 建筑行业事故预防：综合动态事故致因理论的应用
- 北斗卫星监测系统在电网塔形实时监控中的应用
- 煤层气羽状水平井数值模拟：交替隐式算法的应用
- 开放字符串T对偶与双空间坐标变换
- 煤矿瓦斯抽采半径测定新方法——瓦斯储量法
- 大倾角大采高工作面设备稳定与安全控制关键技术
- 超标违规背景下的热波动影响分析
- 中国煤矿选煤设计进展与挑战：历史、现状与未来发展
- 反演技术与RBF神经网络在移动机器人控制中的应用
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
