Informed Sampling-based Collision Avoidance with Least Deviation from the Nominal Path Thomas T. Enevoldsen1and Roberto Galeazzi1

2025-05-05 0 0 641.55KB 7 页 10玖币

Informed Sampling-based Collision Avoidance with Least Deviation

from the Nominal Path

Thomas T. Enevoldsen1and Roberto Galeazzi1

including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers

or lists, or reuse of any copyrighted component of this work in other works.

Abstract— This paper addresses local path re-planning for

n-dimensional systems by introducing an informed sampling

scheme and cost function to achieve collision avoidance with

minimum deviation from an (optimal) nominal path. The

proposed informed subset consists of the union of ellipsoids

along the speciﬁed nominal path, such that the subset efﬁciently

encapsulates all points along the nominal path. The cost func-

tion penalizes large deviations from the nominal path, thereby

ensuring current safety in the face of potential collisions while

retaining most of the overall efﬁciency of the nominal path.

The proposed method is demonstrated on scenarios related to

the navigation of autonomous marine crafts.

I. INTRODUCTION

The collision avoidance system is a crucial component

for the safe motion control of autonomous systems seeking

widespread adoption across different industrial sectors, such

as collective mobility, precision farming, intermodal logis-

tics, smart manufacturing. In all these industrial processes the

operations carried out by or with the support of autonomous

systems are characterized by some combination of metrics

of efﬁciency – e.g., minimum time, minimum energy, mini-

mum distance –, and safety. The efﬁcient execution of such

operations implies the adherence to an (optimal) nominal

path by the autonomous bus [1], [2], autonomous ship [3]

or autonomous robot [4]. At the mission planning stage

it is hard to account for the dynamically changing local

environments. Hence, there is the need for a path planner

that computes optimal local deviations from the nominal path

to ensure current safety while retaining most of the overall

efﬁciency of nominal path, whenever a collision may disrupt

the ongoing operation.

Sampling-based motion planners are highly efﬁcient at

addressing complex planning problems with multiple con-

straints, such as those posed by collision avoidance and au-

tonomous navigation tasks. Mechanisms and techniques for

computing paths that minimize path length using sampling-

based methods are widespread in current literature [5], [6],

with one of the most inﬂuential methods being the Informed

RRT* [7], which reduces the sampling space to an informed

subset, contained within an ellipsoid, once an initial path is

obtained. The informed set guarantees that it contains any

point that can improve the solution, whilst increasing the

This research is sponsored by the Danish Innovation Fund, The Danish

Maritime Fund, Orients Fund and the Lauritzen Foundation through the

Autonomy part of the ShippingLab project, Grant number 8090-00063B.

The sea charts have been provided by the Danish Geodata Agency.

1Automation and Control Group, Department of Electrical and Photonics

Engineering, Technical University of Denmark, DK-2800 Kgs. Lyngby,

Denmark {tthen,roga}@dtu.dk

(a) N= 250, cd(σ) = 895 (b) N= 500, cd(σ) = 285

Fig. 1: Informed sampling strategy for computing the min-

imum path deviation, where an ellipsoidal subset is formed

along each segment of the nominal trajectory. The nominal

trajectory (magenta) is obstructed by some obstacles, and

therefore the planned path (red) is computed to circumvent

these whilst minimizing the deviation from the nominal path.

probability that the solution cost is decreased by sampling

within the subset. However, these methods typically seek

to minimize path length, where for collision avoidance one

may instead wish to efﬁciently compute paths with minimal

deviation from a nominal.

This paper focuses on local path re-planning for n-

dimensional systems which have an (optimal) nominal path

to achieve collision avoidance in dynamic environments, and

it makes the following contributions. First, we propose an

extension to the concept of the informed subset to allow for

convergence towards solutions with minimum path deviation.

This is achieved by introducing a cost function, which

allows the underlying algorithm to minimize with respect to

the nominal path. The extension involves forming multiple

overlapping informed subsets along the nominal path, which

results in an informed set composed of the union of multiple

ellipsoidal subsets (Fig. 1). Last, a switching condition and

additional sampling biasing are proposed to allow for rapid

convergence towards the nominal path.

A. Related work

Optimal Sampling-based Motion Planning (SBMP) came

to fruition when [8] introduced RRT* and PRM*, which are

asymptotically optimal in probability [6]. To improve the

convergence rate and performance of RRT*, [7], [9] proposed

arXiv:2210.13199v1 [cs.RO] 24 Oct 2022

the Informed RRT*, which reduces the sampling space to

an ellipsoidal subset once an initial solution is found. This

increases the probability that each subsequent sample has

a greater likelihood of improving the current best found

solution. The concept of the informed subset then became

an integral part of other SBMP algorithms [10], [11], [12].

Current research aims at extending the capabilities of the

informed subset to further accelerate convergence to certain

classes of solutions. Recently, [13] identiﬁes smaller in-

formed sets within the informed set itself, using the notion of

a beacon, and thereby honing the search. In [14] the authors

also propose a method for identifying subregions within the

informed set. [15] specializes an informed sampling scheme

that decreases the size of the search space to produce paths

that abide by the maritime rules-of-the-road. [16] slides

an informed subset along the found path, computing local

solutions of minimum path length. The work by [17] utilizes

a pre-computed gridmap in order to ﬁnd an initial solution

quickly, such that the informed subset [7] can be applied

sooner. [18] proposes a scheme for sampling generalized

informed sets using Markov Chain Monte Carlo, allowing for

arbitrarily shaped non-convex informed sets. [19] proposes to

inform the planning algorithm about the manipulation task

of mobile manipulators, i.e. a sequence of poses the end-

effector must reach, by introducing it as success criterion

when computing the movement of the mobile base. [6] details

a general overview of the state-of-the-art in optimal SBMP.

Within the ﬁelds of self-driving cars and autonomous

marine systems, SBMP has gotten a foothold. [20] and [21]

survey the application of various motion planning techniques

for autonomous vehicles, providing insight into the use of

SBMP for driving in urban environments and highways,

respectively. [22] proposes a method for repairing existing

trajectories, where infeasible parts of the nominal trajectory

are repaired to compute feasible deviations. [23] discretizes

the nominal trajectory and places guide points in locations

that are infeasible with the nominal, and thereby biases

the sampling. [24] uses an estimated nominal path, such

as from a Voronoi graph, to guide the RRT exploration

through cluttered environments. [25] explores a sampling-

based scheme that compute paths, which are similar in

curvature to the nominal path. Whereas within the realm of

discrete planning, algorithms such as lifelong planning A*

[26] and D*-lite [27] concern efﬁcient re-planning.

In the maritime domain, SBMP algorithms are favoured

due to the existence of both the complex constraints and

environments. [28] investigates using a non-holonomic RRT

for collision avoidance. [3], [29] and [30] utilize RRT*

for collision avoidance, taking various other metrics into

account, such as minimizing nominal path deviation, speed

loss, curvature and grounding risk.

The reviewed literature emphasizes two main aspects: The

informed set is a powerful and effective concept to channel

the sampling effort of SBMP algorithms and achieve faster

convergence to the optimal path; SBMP algorithms have

been used to plan between the start and goal states for

designing both nominal paths and path alterations along

a single straight segment of a nominal path. This paper

advances the application of informed SBMP algorithms to

collision avoidance along multi-segment paths by introducing

an extended informed set and a cost function that penalizes

deviations from the nominal path.

II. PRELIMINARIES

The general formulation of the optimal sampling-based

motion planning problem is now presented, as well as the

formalization of the informed subset as proposed by [7].

A. Optimal sampling-based motion planning

Let X ⊆ Rnbe the state space, with xdenoting the state.

The state space is composed of two subsets: the free space

Xfree, and the obstacles Xobs, where Xfree =X\Xobs. The

states contained within Xfree are all states that are feasible

with respect to the constraints posed by the system and the

environment. Let xstart ∈Xfree be the initial state at some

time t= 0 and xend ∈Xfree the desired ﬁnal state at some

time t=T. Let σ: [0,1] 7→ Xfree be a sequence of states that

constitutes a found path, and Σbe the set of all feasible and

nontrivial paths. The objective is then to ﬁnd the optimal path

σ∗, which minimizes a cost function c(·), while connecting

xstart to xend through states xi∈Xfree,

σ∗= arg min

σ∈Σ{c(σ)|σ(0) = xstart , σ(1) = xend ,

∀s∈[0,1], σ(s)∈Xfree }.

(1)

The most commonly adopted cost function is the Eu-

clidean path length, which gives rise to the shortest path

problem. Given a path σconsisting of nstates, the Euclidean

path length is given by

cl(σ) =

i=1 kxi−xi−1k2,∀xi∈σ. (2)

The cost function is additive, i.e. given a sequence of nstates

and some index kthe following equality holds true

c((x0,...,xn)) = c((x0,...,xk)) + c((xk,...,xn)) (3)

Therefore, whenever a new node or edge is added, the cost

to go from the root to the nearest node, together with the

cost from the nearest node to the new node, is computed as

c(σ) = c((xstart,...,xnearest)) + c((xnearest,xnew)) (4)

as required by the underlying SBMP [8].

B. Informed sampling

The concept of an informed sampling space was intro-

duced by [7] with the Informed RRT*. It was shown that

the reduction of the sampling region to an informed subset

increased the probability that each subsequent sample would

improve the current best found solution. In the case of [7], [9]

an informed subset for the euclidean distance was formulated

as an ellipsoid, and was given by

Xˆ

f={x∈ X |kxstart −xk2+kx−xendk2≤cbest}(5)

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

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

10 玖币 0人已下载

立即下载

摘要：

InformedSampling-basedCollisionAvoidancewithLeastDeviationfromtheNominalPathThomasT.Enevoldsen1andRobertoGaleazzi1©2022IEEE.Personaluseofthismaterialispermitted.PermissionfromIEEEmustbeobtainedforallotheruses,inanycurrentorfuturemedia,includingreprinting/republishingthismaterialforadvertisingorpromo...

展开>> 收起<<

Informed Sampling-based Collision Avoidance with Least Deviation from the Nominal Path Thomas T. Enevoldsen1and Roberto Galeazzi1.pdf

共7页,预览2页

还剩页未读，继续阅读

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

Informed Sampling-based Collision Avoidance with Least Deviation from the Nominal Path Thomas T. Enevoldsen1and Roberto Galeazzi1

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: