A Rapidly-Exploring Random Trees Motion Planning Algorithm for Hybrid Dynamical Systems

2025-04-30 0 0 408.76KB 18 页 10玖币

侵权投诉

A Rapidly-Exploring Random Trees

Motion Planning Algorithm for Hybrid

Dynamical Systems*

Nan Wang and Ricardo G. Sanfelice∗†

October 28, 2022

Abstract

This paper proposes a rapidly-exploring random trees (RRT) algo-

rithm to solve the motion planning problem for hybrid systems. At

each iteration, the proposed algorithm, called HyRRT, randomly picks

a state sample and extends the search tree by ﬂow or jump, which is

also chosen randomly when both regimes are possible. Through a def-

inition of concatenation of functions deﬁned on hybrid time domains,

we show that HyRRT is probabilistically complete, namely, the proba-

bility of failing to ﬁnd a motion plan approaches zero as the number of

iterations of the algorithm increases. This property is guaranteed un-

der mild conditions on the data deﬁning the motion plan, which include

a relaxation of the usual positive clearance assumption imposed in the

literature of classical systems. The motion plan is computed through

the solution of two optimization problems, one associated with the

ﬂow and the other with the jumps of the system. The proposed algo-

rithm is applied to a walking robot so as to highlight its generality and

computational features.

1 Introduction

Motion planning consists of ﬁnding a state trajectory and associated inputs,

connecting the initial and ﬁnal state while satisfying the dynamics of the

∗*Research partially supported by NSF Grants no. ECS-1710621, CNS-2039054, and

CNS-2111688, by AFOSR Grants no. FA9550-19-1-0053, FA9550-19-1-0169, and FA9550-

20-1-0238, and by ARO Grant no. W911NF-20-1-0253.

†Nan Wang and Ricardo G. Sanfelice are with the Department of Electrical

and Computer Engineering, University of California, Santa Cruz, CA 95064, USA;

nanwang@ucsc.edu, ricardo@ucsc.edu

arXiv:2210.15082v1 [cs.RO] 26 Oct 2022

system as well as a given safety criterion. Motion planning problems for

purely continuous-time systems and purely discrete-time systems have been

well studied in the literature; see, e.g., [1]. In recent years, various planning

algorithms have been developed to solve motion planning problems, from

graph search algorithms [2] to artiﬁcial potential ﬁeld methods [3]. A main

drawback of graph search algorithms is that the number of vertices grows

exponentially as the dimension of states grows, which makes computing

motion plans ineﬃcient for high-dimensional systems. The artiﬁcial poten-

tial ﬁeld method suﬀers from getting stuck at local minimum. Arguably,

the most successful algorithm to solve motion planning problems for purely

continuous-time systems and purely discrete-time systems is the sampling-

based RRT algorithm [4]. This algorithm incrementally constructs a tree

of state trajectories toward random samples in the state space. Similar to

graph search algorithms, RRT suﬀers from the curse of dimensionality, but,

in practice, achieves rapid exploration in solving high-dimensional motion

planning problems [5]. Compared with the artiﬁcial potential ﬁeld method,

RRT is probabilistically complete [6], which means that the probability of

failing to ﬁnd a motion plan converges to zero, as the number of samples

approaches inﬁnity.

While RRT algorithms have been used to solve motion planning problems

for purely continuous-time systems [6] and purely discrete-time systems [7],

fewer eﬀorts have been devoted to applying RRT-type algorithms to solve

motion planning problems for systems with combined continuous and dis-

crete behavior. In [8], a hybrid RRT algorithm is proposed for motion

planning problems for a special class of hybrid systems, which follows the

classical RRT scheme but does not establish key properties of the algorithm,

such as probabilistic completeness.

This paper focuses on motion planning problems for hybrid systems mod-

eled as hybrid equations [9]. In this modeling framework, diﬀerential and

diﬀerence equations with constraints are used to describe the continuous

and discrete behavior of the hybrid system, respectively. This general hy-

brid system framework can capture most hybrid systems emerging in robotic

applications, not only the class of hybrid systems considered in [8], but also

systems with memory states, timers, impulses, and constraints. For this

broad class of hybrid systems, a motion planning algorithm is proposed in

this paper. Following [6], the proposed algorithm, called HyRRT, incre-

mentally constructs search trees, rooted in the initial state set and toward

the random samples. At ﬁrst, HyRRT draws samples from the state space.

Then, it selects the vertex such that the state associated with this vertex

has minimal distance to the sample. Next, HyRRT propagates the state tra-

jectory from the state associated with the selected vertex. Following [10], it

is established that, under certain assumptions, HyRRT is probabilistically

complete. To the authors’ best knowledge, HyRRT is the ﬁrst RRT-type

algorithm for systems with hybrid dynamics that is probabilistically com-

plete. The proposed algorithm is applied to a walking robot example so as

to assess its capabilities.

The remainder of the paper is structured as follows. Section 2 presents

notation and preliminaries. Section 3 presents the problem statement and

introduction of application. Section 4 presents the HyRRT algorithm. Sec-

tion 5 presents the analysis of the probabilistic completeness of HyRRT

algorithm. Section 6 presents the illustration of HyRRT in the example.

Due to space constraints, proofs will be published elsewhere.

2 Notation and Preliminaries

2.1 Notation

The real numbers are denoted as Rand its nonnegative subset is denoted

as R≥0. The set of nonnegative integers is denoted as N. The notation int I

denotes the interior of the interval I. The notation Sdenotes the closure of

the set S. The notation ∂S denotes the boundary of the set S. Given sets

P⊂Rnand Q⊂Rn, the Minkowski sum of Pand Q, denoted as P+Q,

is the set {p+q:p∈P, q ∈Q}. The notation |·| denotes the Euclidean

norm. The notation rge fdenotes the range of the function f. Given a

point x∈Rnand a subset S⊂Rn, the distance between xand Sis denoted

dist(x, S) := infs∈S|x−s|. The notation Bdenotes the closed unit ball of

appropriate dimension in the Euclidean norm.

2.2 Preliminaries

A hybrid system Hwith inputs is modeled as [9]

H:(˙x=f(x, u) (x, u)∈C

x+=g(x, u) (x, u)∈D(1)

where x∈Rnis the state, u∈Rmis the input, C⊂Rn×Rmrepresents

the ﬂow set, f:Rn×Rm→Rnrepresents the ﬂow map, D⊂Rn×Rm

represents the jump set, and g:Rn×Rm→Rnrepresents the jump map,

respectively. The continuous evolution of xis captured by the ﬂow map f.

The discrete evolution of xis captured by the jump map g. The ﬂow set C

collects the points where the state can evolve continuously. The jump set D

collects the points where jumps can occur.

Given a ﬂow set C, the set UC:= {u∈Rm:∃x∈Rnsuch that (x, u)∈

C}includes all possible input values that can be applied during ﬂows. Simi-

larly, given a jump set D, the set UD:= {u∈Rm:∃x∈Rnsuch that (x, u)∈

D}includes all possible input values that can be applied at jumps. These

sets satisfy C⊂Rn×UCand D⊂Rn×UD. Given a set K⊂Rn×U?,

where ?is either Cor D, we deﬁne Π?(K) := {x:∃u∈U?s.t. (x, u)∈K}

as the projection of Konto Rn, and deﬁne C0:= ΠC(C) and D0:= ΠD(D).

In addition to ordinary time t∈R≥0, we employ j∈Nto denote the

number of jumps of the evolution of xand ufor Hin (1), leading to hybrid

time (t, j) for the parameterization of its solutions and inputs. The domain

of a solution to His given by a hybrid time domain. A hybrid time domain

is deﬁned as a subset Eof R≥0×Nthat, for each (T, J)∈E,E∩([0, T ]×

{0,1, ..., J}) can be written as ∪J

j=0([tj, tj+1], j) for some ﬁnite sequence of

times 0 = t0≤t1≤t2≤... ≤tJ+1 =T. A hybrid arc φ: dom φ→Rn

is a function on a hybrid time domain that, for each j∈N,t7→ φ(t, j)

is locally absolutely continuous on each interval Ij:= {t: (t, j)∈dom φ}

with nonempty interior. The deﬁnition of solution pair to a hybrid system

is given as follows. For more details, see [9].

Deﬁnition 2.1. (Solution pair to a hybrid system) Given a pair of functions

φ: dom φ→Rnand u: dom u→Rm,(φ, u)is a solution pair to (1) if

dom(φ, u) := dom φ= dom uis a hybrid time domain, (φ(0,0), u(0,0)) ∈

C∪D, and the following hold:

1) For all j∈Nsuch that Ijhas nonempty interior,

a) the function t7→ φ(t, j)is locally absolutely continuous,

b) (φ(t, j), u(t, j)) ∈Cfor all t∈int Ij,

c) the function t7→ u(t, j)is Lebesgue measurable and locally bounded,

d) for almost all t∈Ij,˙

φ(t, j) = f(φ(t, j), u(t, j)).

2) For all (t, j)∈dom(φ, u)such that (t, j + 1) ∈dom(φ, u),

(φ(t, j), u(t, j)) ∈D φ(t, j + 1) = g(φ(t, j), u(t, j)).

HyRRT requires concatenating solution pairs. The concatenation oper-

ation of solution pairs is deﬁned next.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

ARapidly-ExploringRandomTreesMotionPlanningAlgorithmforHybridDynamicalSystems*NanWangandRicardoG.Sanfelice*October28,2022AbstractThispaperproposesarapidly-exploringrandomtrees(RRT)algo-rithmtosolvethemotionplanningproblemforhybridsystems.Ateachiteration,theproposedalgorithm,calledHyRRT,randomlypick...

展开>> 收起<<

A Rapidly-Exploring Random Trees Motion Planning Algorithm for Hybrid Dynamical Systems.pdf

共18页,预览4页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

A Rapidly-Exploring Random Trees Motion Planning Algorithm for Hybrid Dynamical Systems

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: