Data-Driven Convex Approach to Off-road Navigation via Linear Transfer Operators

2025-08-18 2 0 1.05MB 8 页 10玖币

侵权投诉

arXiv:2210.00723v2 [eess.SY] 1 May 2023

Data-Driven Convex Approach to Off-road

Navigation via Linear Transfer Operators

Joseph Moyalan, Yongxin Chen and Umesh Vaidya

Abstract—We consider the problem of optimal control design

for navigation on off-road terrain. We use a traversability

measure to characterize the difﬁculty of navigation on off-road

terrain. The traversability measure captures terrain properties

essential for navigation, such as elevation maps, roughness,

slope, and texture. The terrain with the presence or absence of

obstacles becomes a particular case of the proposed traversability

measure. We provide a convex formulation to the off-road

navigation problem by lifting the problem to the density space

using the linear Perron-Frobenius (P-F) operator. The convex

formulation leads to an inﬁnite-dimensional optimal navigation

problem for control synthesis. We construct the ﬁnite-dimensional

approximation of the optimization problem using data. We use a

computational framework based on the data-driven approxima-

tion of the Koopman operator. This makes the proposed approach

data-driven and applicable to cases where an explicit system

model is unavailable. Finally, we apply the proposed navigation

framework with single integrator dynamics and Dubin’s car

model.

Index Terms—Motion and Path Planning, Optimization and

Optimal Control, Model Learning for Control

I. INTRODUCTION

NAVIGATION problem is one of the most critical research

ﬁelds in the robotics community. More recently, the

problem of off-road navigation, driven by robotics applications

in an unstructured environment, has received much atten-

tion. The objective is to drive a robot/vehicle from some

initial set to the desired target set through a terrain where

traversability varies continuously over the entire domain of

interest. This is in contrast to navigation in the presence

of obstacles where the regions with obstacles are prohibited

and hence not traversable. There is extensive literature on

navigation in the presence of obstacles. Navigation function

and potential function are used for navigation in the presence

of obstacles [1]–[4]. While the potential function could have

local minima preventing the navigation from initial set to the

target, the navigation function is hard to ﬁnd. The control

barrier functions (CBFs) are also used for navigation with

safety constraints [5]. CBFs combine ideas from the control

Lyapunov function and barrier certiﬁcates for invariance to

ensure safety. However, ﬁnding CBFs suffer from the same

challenges as ﬁnding control Lyapunov function and cannot

be easily adapted for navigation in off-road terrain where the

deﬁnition of safety itself is nebulous.

Financial support from NSF under grants 1942523, 2008513, 2031573 and

NSF CPS award 1932458 is greatly acknowledged. J. Moyalan and U. Vaidya

are with the Department of Mechanical Engineering, Clemson University,

Clemson, SC; {jmoyala,uvaidya}@clemson.edu. Y. Chen is with the School

of Aerospace Engineering, Georgia Institute of Technology, Atlanta, GA;

{yongchen}@gatech.edu

The problem of off-road navigation has attracted more

interest recently. In [6], perception is used to determine the

terrain traversability and local control strategy for navigation.

Most of the current literature on this topic has been using

sensor data from LIDAR, cameras, and GPS/IMUs to map

the off-road terrain to generate a traversability map [7]–

[10]. An existing algorithm such as A⋆is used to design

traversable paths in the off-road environment. However, due to

the nonconvex nature of the traversability map and hence the

cost, the problem becomes nonconvex and, therefore, difﬁcult

to solve with no guarantee of global optimality.

One of this paper’s main contributions is providing a convex

formulation to the off-road navigation problem. The convex

formulation is made possible by transforming the problem in

the dual space of densities. The formulation of optimal control

problem in the dual space of densities is proposed in [11],

[12], and its extension to navigation problem in the presence

of deterministic and stochastic obstacles is studied in [13]–

[15]. This paper focuses on the off-road navigation problem

for a given traversability map. The terrain traversability map

includes information about the difﬁculty level in navigating.

The terrain’s traversability measure depends on terrain param-

eters such as elevation map, roughness, slope, and texture.

Therefore, we have utilized the normalized elevation map

while constructing the traversability measure.

The convex formulation leads to an inﬁnite-dimensional

convex optimization problem for the off-road navigation prob-

lem. First, we use data to construct the ﬁnite-dimensional

approximation of the inﬁnite-dimensional convex problem.

Then, we use a computational framework based on the data-

driven approximation of linear Koopman and Perron-Frobenius

(P-F) operators for the ﬁnite-dimensional approximation of

the inﬁnite-dimensional convex optimization problem. The

second main contribution is providing a numerically efﬁcient

computational algorithm for the data-driven approximation

of the P-F operator, preserving some natural properties of

this operator. Finally, we demonstrate the application of the

developed framework for off-road navigation of vehicle dy-

namics with the Dubin car model. We also compare the results

obtained using our proposed approach with the existing A⋆

algorithm. The study’s main ﬁnding is that the traversability

cost associated with A⋆is more than one computed using our

proposed approach.

The rest of the paper is structured as follows. Section II

consists of problem formulation, and we discuss the main

results in Section III. Then, in Section IV, we develop the

computational framework based on the linear operator frame-

work. Finally, we present the simulation results in Section V,

and a conclusion is in Section VI.

II. PROBLEM FORMULATION FOR OFF-ROAD NAVIGATION

This section deﬁnes the traversability map, which will be

later used in the convex formulation of the navigation problem.

We will also motivate the choice of the cost function for

off-road navigation. Let us consider the following dynamical

system in control afﬁne form as

x=f(x) + g(x)u(1)

where x∈X⊂Rnand u∈U⊂Rmare the states

and control input respectively. We assume that f(x),g(x)∈

C1(X,Rn), i.e. the space of continuously differentiable func-

tions on X. The dynamical control system is assumed to model

the control dynamics of the vehicle. The control-afﬁne form

is not restrictive, and this will typically be the case for the

robotics and vehicle dynamics application [16], [17].

Notations: We consider B(x)to be the Borel σ-algebra on

Xand M(X)as the vector space of real-valued measures on

B(X). Let L∞(X)and L1(X)be the space of essentially

bounded and integrable functions on Xrespectively. The

notations in bold and lower case will represent vectors and

notations in bold and upper case will represent matrices. Also,

st(x)is the notation for the trajectory of feedback system

x=f(x) + g(x)k(x)starting from initial condition xat time

t∈R, where u=k(x)∈ C1(X,Rm)is the feedback input.

Similarly, s−t(x)represents the closed-loop trajectory as the

function of initial condition xbackward in time.

A. Traversability Map

We assume that the traversability description of the terrain

is captured by a nonnegative function b(x)∈ L1(X). We

assume that the function b(x)captures the information of the

elevation map, terrain roughness, slope, and terrain texture.

The construction of such a map is an active area of interest

where onboard sensors on the vehicles such as vision, LIDAR,

and IMU, as well as drone sensory images, can be used

to construct such maps [18]–[20]. We propose the following

deﬁnition of traversability measure, which captures the relative

degree of difﬁculty of traversing unstructured terrain.

Deﬁnition 1. Let µb∈ M(X)be the associated traversability

measure, i.e., dµb(x) = b(x)dx, where b(x)≥0is assumed

to be an integrable function and is zero on the ﬁnal target set,

XT. For any set A∈ B(X), the traversability of the set Ais

deﬁned using b(x)as

Trav(A) := ZA

b(x)dx=: µb(A).(2)

Trav(A)captures the relative difﬁculty of traversing

through the region A⊂X. In particular, if µb(A1)< µb(A2)

where Ai∈ B(X), then the region A2is more difﬁcult to

traverse than region A1. It is easy to see that the above deﬁni-

tion of traversability measure also captures the information of

binary obstacles. In particular, if Xuis an obstacle set, then

we can describe it using

b(x) = 1

λ(Xu)1Xu(x)(3)

where λ(·)is the Lebesgue measure and 1Xuis the indicator

function of the set Xu. The main objective of this paper

involves determining the control inputs uto navigate the

vehicle dynamics from some initial state X0to some ﬁnal

target set XTwhile keeping the traversability cost below some

threshold, say γ, i.e.,

Z∞

b(x(t))dt ≤γ(4)

where x(t)is the trajectory of the control system (1). In this

paper, we are interested in the asymptotic navigation problem,

where the objective is to ﬁnd the shortest distance path to

the target and the control cost. In particular, we consider the

following cost function

min

uV(x) = min

uZ∞

q(x(t)) + u⊤Rudt. (5)

where q(x)is the distance function which is zero at the target

set XT, and R>0is the positive deﬁnite matrix. Instead of

minimizing the cost function from every initial condition xas

in (5), our proposed convex formulation relies on minimizing

the following cost function averaged over all states x∈X0.

min

uJ(µ0) = min

uZX

V(x)dµ0(x)(6)

where µ0is the measure capturing the distribution of the initial

state. In particular, for the initial state of the vehicle in set X0,

we have measure µ0supported on set X0. The form of the

cost function where V(x)is averaged over the state x∈X0

plays a fundamental role in the convex formulation of optimal

navigation problem in the space of density.

In the rest of the paper, we will assume that µ0is absolutely

continuous with density function h0, i.e., dµ0

dx=h0(x). For

example if µ0is supported on initial set then h0(x) = 1X0(x)

i.e., indicator function of set X0. The objective is to ﬁnd the

feedback controller k(x)to minimize the cost function in (6).

Appropriate conditions on the initial measure µ0are necessary

to ensure the cost function is ﬁnite. We make sure that the

density function h0is ﬁnite and positive semi-deﬁnite on X

and h0∈ L1(X)∩ C1(X).

Along with minimizing the cost function, it is also of

interest to avoid certain obstacle sets, Xu, and limit the control

authority, i.e., |uj| ≤ Lj. The obstacle avoidance constraints

for almost every trajectory starting from the initial set X0are

written as

1Xu(x(t))dµ0(x) = 0,∀t≥0

where x(t)is the solution of system (1) starting from initial

condition x. With the above deﬁnition, we can state the

problem statement for optimal off-road navigation using the

traversability map as given below.

Problem 1. (Optimal off-road Navigation Problem) Navigate

almost every system trajectory for (1) starting from the initial

set X0to the target set XTwhile avoiding the obstacle set

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

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

10 玖币 0人已下载

立即下载

摘要：

arXiv:2210.00723v2[eess.SY]1May20231Data-DrivenConvexApproachtoOff-roadNavigationviaLinearTransferOperatorsJosephMoyalan,YongxinChenandUmeshVaidyaAbstract—Weconsidertheproblemofoptimalcontroldesignfornavigationonoff-roadterrain.Weuseatraversabilitymeasuretocharacterizethedifﬁcultyofnavigationonoff-r...

展开>> 收起<<

Data-Driven Convex Approach to Off-road Navigation via Linear Transfer Operators.pdf

共8页,预览2页

还剩页未读，继续阅读

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

Data-Driven Convex Approach to Off-road Navigation via Linear Transfer Operators

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: