A Tree Structure Approach to Reachability Analysis Alessandro Alla and Peter M. Dower and Vincent Liu Abstract Reachability analysis is a powerful tool when it comes to capturing the behaviour thus verifying the safety

2025-04-30 0 0 953.39KB 15 页 10玖币

侵权投诉

A Tree Structure Approach to Reachability Analysis

Alessandro Alla and Peter M. Dower and Vincent Liu

Abstract Reachability analysis is a powerful tool when it comes to capturing the behaviour, thus verifying the safety,

of autonomous systems. However, general-purpose methods, such as Hamilton-Jacobi approaches, suﬀer from the

curse of dimensionality. In this paper, we mitigate this problem for systems of moderate dimension and we propose

a new algorithm based on a tree structure approach with geometric pruning. The numerical examples will include a

comparison with a standard ﬁnite-diﬀerence method for linear and nonlinear problems.

Keywords: Reachability analysis, Hamilton-Jacobi equations, optimal control, tree structure, convex geometry

1 Introduction

The development and production of self-driving cars and the deployment of drones in industrial applications are

exemplars of society’s ever-increasing fascination of autonomous vehicles. Commensurate to the growing integration

of these vehicles in day-to-day life is the concern regarding how safe these unmanned vehicles are. These concerns are

particularly prevalent in safety-critical applications such as human-robot interactions, disaster responses, and the use

of high-value machinery. In such applications, being able to characterize all possible behaviours of these autonomous

vehicles would be a rigorous way to verify their safety. Reachable sets lend themselves well towards this goal. When

computed forwards in time, they characterise all possible states that can be reached using a constraint admissible control

from some initial set of states. Similarly, when computed backwards in time, they characterise all possible states that

are able to reach a terminal set of states using a constraint admissible control.

The computation of reachable sets may be done via the Hamilton-Jacobi-Bellman (HJB) equations, i.e. one of the

most powerful formal veriﬁcation tools for guaranteeing performance and safety properties of systems. This approach

is rather general and works for controlled nonlinear systems that involve disturbances or adversarial behaviors, and

despite this, characterizes the exact reachable set rather than approximations. However, this method suﬀers from the

curse of dimensionality and it is hard to build numerical methods for high dimensional problems. In the last two

decades several contributions on the mitigitation of the curse of dimensionality have been investigated mainly for

optimal control problems such as, e.g. model order reduction [1, 2], tree structure algorithms [3, 4], spectral methods

Alessandro Alla

Department of Molecular Sciences and Nanosystems, Università Ca’ Foscari Venezia

e-mail: alessandro.alla@unive.it

Peter M. Dower

Department of Electrical and Electronic Engineering, The University of Melbourne

e-mail: pdower@unimelb.edu.au

Vincent Liu

Department of Electrical and Electronic Engineering, The University of Melbourne

e-mail: liuv2@studentunimelb.edu.au

arXiv:2210.13779v2 [math.OC] 26 Oct 2022

[5], max-plus algebra [6, 7], Hopf-Lax approaches [8, 9], neural networks [10, 11], tensor decomposition [12, 13] and

sparse grids method [14].

For the approximation of the reachable sets in [15], the authors provides a formulation that requires numerically

solving a Hamilton-Jacobi partial diﬀerential equation. This is a grid-based approach which is typically limited to

systems of no more than 4 states on standard computers. Therefore, the study of higher dimensional problems remains

an open research area. Under certain assumption on the system, one could decompose it appropriately, and obtain

eﬃcient algorithms for computing reachable sets, see e.g. [16]. Other approaches have been studied in [17] where

reachable sets for nonlinear systems are computed via results on reachability for uncertain linear system. Linearisation

error is explicitly accounted for in [17] using an iterative algorithm to bound this error in an over-approximative manner.

Similarly, in [18], uncertain linear systems are considered with a focus on producing zonotopic under-approximations

of reachable sets. In their work, the representational complexity of the reachable sets grows as the algorithm iterates in

time, thus motivating the use of a ‘pruning’ step, which reduces the order of the zonotopic sets.

In this paper, we present an algorithm based on a tree structure to approximate the HJB equation for backwards

reachable sets. The idea of the algorithm is based on the paper [3] and approximates the value function using the

Dynamic Programming Principle (DPP) on an unstructured mesh for optimal control problems. The idea of our

proposed algorithm is as follows.

We start from a discretization of the terminal set and compute the value function on those points. Then, we neglect

the interior points, say those nodes for which the value function is strictly negative. This is a pruning strategy that aims

to mitigate the exponential increase in the cardinality of the tree. We then evolve these nodes backwards in time, making

use of a result provided in Section 4, where the forward controlled dynamical system is equivalent, up to minor changes

in the problem, to the backward system. This is the main diﬀerence with respect to the method in [3]. We are able, in

this work, to compute the tree backwards in time and to prune the tree using the information from the value function.

Our pruning is based on geometric considerations where the interior of the reachable set is pruned. This comes from

the observation, which is demonstrated in this work, that the boundary of the reachable set at a particular time cannot

evolve from the interior of the reachable set at a prior time. Thus, it is wasteful to propagate the tree structure of [3] for

nodes that lie interior to the reachable set. When the value function is convex, interior nodes can be easily identiﬁed

using oﬀ-the-shelf algorithms for computing convex hulls.

The outline of the paper is the following. In Section 2 we present the control problem setup and in Section 3 we

provide the relevant background for the characterization of the backwards reachable set. In Section 4 we show the

equivalence between backwards and forwards reachable sets. Our algorithm is introduced and discussed in Section 5.

Numerical examples are then shown in Section 6. Finally, conclusions and future works are discussed in Section 7.

Notation

•Let I𝑛denote an 𝑛-by-𝑛identity matrix.

•Let h·,·i denote the Euclidean inner product.

•Let k𝑤kdenote any norm of a vector 𝑤.

•Let 𝑖𝑛𝑡 (A), 𝑐𝑙 (A), and 𝜕Adenote the interior, closure, and boundary of a set A, respectively.

•Let C𝑘(Ω;R)denote the space of 𝑘-times continuously diﬀerentiable functions from Ωto Rwith CC0.

•Let B𝑅(𝑥0){𝑥∈R𝑛| k𝑥−𝑥0k ≤ 𝑅}denote a ball of radius 𝑅≥0with centre 𝑥0∈R𝑛.

•An ellipsoidal set with centre 𝑞and shape 𝑄is deﬁned as

E(𝑞, 𝑄)𝑥∈R𝑛| (𝑥−𝑞)𝑇𝑄−1(𝑥−𝑞) ≤ 1,(1)

where 𝑞∈R𝑛and 𝑄∈R𝑛×𝑛is a symmetric, positive deﬁnite matrix. The axes of E(𝑞, 𝑄)are aligned with the

eigenvectors of 𝑄with lengths along these axes being equal to the square root of the corresponding eigenvalues.

•Let conv (A)denote the convex hull of a ﬁnite set of points A={𝑎𝑖}𝑖∈{1,··· ,𝑛𝑝}, deﬁned by

conv (A)=(𝑛𝑝



𝑖=1

𝜆𝑖𝑎𝑖𝜆𝑖≥0for all 𝑖∈ {1,· · · , 𝑛𝑝}and

𝑛𝑝



𝑖=1

𝜆𝑖=1).(2)

2 Problem Setup

In this section we begin with a system description and review relevant background relating to optimal control. Consider

the continuous-time nonlinear system described by

¤𝑥(𝑡)=𝑓(𝑥(𝑡), 𝑢(𝑡)),∀𝑡∈ (0, 𝑇),(3)

where 𝑇≥0,𝑥(𝑡) ∈ R𝑛is the state and 𝑢(𝑡) ∈ Uis the input at time 𝑡, with U⊂R𝑚being compact. The input is

selected such that 𝑢∈ U, where

U{𝑢:[0, 𝑇] → U|𝑢measurable}.(4)

The following ﬂow ﬁeld conditions are assumed throughout.

Assumption 1 The function 𝑓:R𝑛×U→R𝑛satisﬁes

i) 𝑓∈ C (R𝑛×U;R𝑛); and

ii) 𝑓is locally Lipschitz continuous in 𝑥, uniformly in 𝑢, i.e. for any 𝑅 > 0, there exists a Lipschitz constant 𝐶𝑓

𝑅>0

such that k𝑓(𝑥, 𝑢) − 𝑓(𝑦, 𝑢)k ≤ 𝐶𝑓

𝑅k𝑥−𝑦k,∀(𝑥, 𝑦, 𝑢) ∈ B𝑅(0) × B𝑅(0) × U.

Under Assumption 1, the system described by (3) admits a unique and continuous solution for any initial condition

𝑥(0)=𝑥0and ﬁxed control 𝑢(·) ∈ U. We denote these solutions at time 0≤𝑡≤𝑇by 𝜑(𝑡; 0, 𝑥0, 𝑢(·)).

Attach to (3) the value function 𝑉:[0, 𝑇] × R𝑛corresponding to the optimal control problem

𝑉(𝑡, 𝑥)inf

𝑢( ·) ∈ U 𝐽(𝑡, 𝑥, 𝑢(·)) inf

𝑢( ·) ∈ U ∫𝑇

𝑡

ℎ(𝜑(𝑠;𝑡, 𝑥, 𝑢(·)), 𝑢(𝑠)) 𝑑𝑠 +𝑔(𝜑(𝑇;𝑡, 𝑥, 𝑢(·))),(5)

where the running cost ℎ:R𝑛×U→Rand the terminal state cost 𝑔:R𝑛→Rsatisfy the assumptions below.

Assumption 2 The functions ℎ:R𝑛×U→Rand 𝑔:R𝑛→Rsatisfy

i) ℎ∈ C (R𝑛×U;R)and 𝑔∈ C (R𝑛;R); and

ii) ℎand 𝑔are locally Lipschitz continuous in 𝑥(uniformly in 𝑢for ℎ), i.e. for any 𝑅 > 0, there exists a Lipschitz

constant 𝐶ℎ

𝑅>0such that |ℎ(𝑥, 𝑢) − ℎ(𝑦, 𝑢)| ≤ 𝐶ℎ

𝑅k𝑥−𝑦k,∀(𝑥, 𝑦, 𝑢) ∈ B𝑅(0) × B𝑅(0) × Uand there exists a

𝐶𝑔

𝑅>0such that |𝑔(𝑥) − 𝑔(𝑦)| ≤ 𝐶𝑔

𝑅k𝑥−𝑦k,∀(𝑥, 𝑦) ∈ B𝑅(0) × B𝑅(0).

The value function deﬁned by (5) satisﬁes the Dynamic Programming Principle (see e.g. [19]), which is presented

below.

Theorem 1 Let Assumptions 1 and 2 hold. Then, for any 𝑡∈ [0, 𝑇],𝑠∈ [0, 𝑡], and 𝑥∈R𝑛, the value function

𝑉:[0, 𝑇] → R𝑛in (5) satisﬁes the Dynamic Programming Principle

𝑉(𝑠, 𝑥)=inf

𝑢( ·) ∈ U ∫𝑡

𝑠

ℎ(𝜑(𝜏;𝑠, 𝑥, 𝑢(·)), 𝑢(𝜏)) 𝑑𝜏 +𝑉(𝑡, 𝜑(𝑡;𝑠, 𝑥, 𝑢(·))).(6)

The value function can be characterized via the viscosity solution of a HJB equation. A detailed discussion on viscosity

solutions can be found in [20].

Theorem 2 Let Assumptions 1 and 2 hold. Then, 𝑉=𝑉(𝑡, 𝑥)in (5) is the unique, and locally Lipschitz continuous

viscosity solution of the HJB equation given by

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

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

10 玖币 0人已下载

立即下载

摘要：

ATreeStructureApproachtoReachabilityAnalysisAlessandroAllaandPeterM.DowerandVincentLiuAbstractReachabilityanalysisisapowerfultoolwhenitcomestocapturingthebehaviour,thusverifyingthesafety,ofautonomoussystems.However,general-purposemethods,suchasHamilton-Jacobiapproaches,suerfromthecurseofdimensional...

展开>> 收起<<

A Tree Structure Approach to Reachability Analysis Alessandro Alla and Peter M. Dower and Vincent Liu Abstract Reachability analysis is a powerful tool when it comes to capturing the behaviour thus verifying the safety.pdf

共15页,预览3页

还剩页未读，继续阅读

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

A Tree Structure Approach to Reachability Analysis Alessandro Alla and Peter M. Dower and Vincent Liu Abstract Reachability analysis is a powerful tool when it comes to capturing the behaviour thus verifying the safety

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: