Safe Planning in Dynamic Environments using Conformal Prediction Lars Lindemann1 Matthew Cleaveland2 Gihyun Shim2 and George J. Pappas2

2025-05-03 0 0 2.45MB 18 页 10玖币

侵权投诉

Safe Planning in Dynamic Environments

using Conformal Prediction

Lars Lindemann∗1, Matthew Cleaveland∗2, Gihyun Shim2, and George J. Pappas2

1Thomas Lord Department of Computer Science, University of Southern California

2Department of Electrical and Systems Engineering, University of Pennsylvania

June 9, 2023

Abstract

We propose a framework for planning in unknown dynamic environments with probabilistic

safety guarantees using conformal prediction. Particularly, we design a model predictive con-

troller (MPC) that uses i) trajectory predictions of the dynamic environment, and ii) prediction

regions quantifying the uncertainty of the predictions. To obtain prediction regions, we use

conformal prediction, a statistical tool for uncertainty quantiﬁcation, that requires availability

of oﬄine trajectory data – a reasonable assumption in many applications such as autonomous

driving. The prediction regions are valid, i.e., they hold with a user-deﬁned probability, so that

the MPC is provably safe. We illustrate the results in the self-driving car simulator CARLA at a

pedestrian-ﬁlled intersection. The strength of our approach is compatibility with state of the art

trajectory predictors, e.g., RNNs and LSTMs, while making no assumptions on the underlying

trajectory-generating distribution. To the best of our knowledge, these are the ﬁrst results that

provide valid safety guarantees in such a setting.

1 Introduction

Mobile robots and autonomous systems operate in dynamic and shared environments. Consider

for instance a self-driving car navigating through urban traﬃc, or a service robot planning a path

while avoiding other agents such as pedestrians, see Fig. 1. These applications are safety-critical

and challenging as the agents’ intentions and policies are unknown so that their a-priori unknown

trajectories need to be estimated and integrated into the planning algorithm. We propose an

uncertainty-informed planning algorithm that enjoys formal safety guarantees by using conformal

prediction.

The problem of path planning in dynamic environments has found broad attention [1]. A large

body of work focused on multi-agent navigation without incorporating predicted agent trajectories,

e.g., the dynamic window approach [2,3] or navigation functions [4–6]. However, predicted trajec-

tories provide additional information and can signiﬁcantly increase the quality of the robot’s path

in terms of safety and performance. Existing works that use trajectory predictions can be broadly

∗Lars Lindemann and Matthew Cleaveland contributed equally.

arXiv:2210.10254v2 [cs.RO] 8 Jun 2023

Figure 1: We predict agent trajectories using state of the art prediction algorithms, such as LSTMs,

and calculate valid prediction regions (blue circles) using conformal prediction.

classiﬁed into two categories: non-interactive and interactive. Non-interactive approaches predict

agent trajectories and then integrate predictions into the planning algorithm [7, 8]. Interactive ap-

proaches simultaneously predict agent trajectories and design the path to take the coupling eﬀect

between a control action and the trajectories of other agents into account [9,10]. While interactive

approaches attempt to model interactions between actions and agents, this is generally a diﬃcult

task and existing works fail to provide quantiﬁable safety guarantees.

In this paper, we focus on designing non-interactive planning algorithms with valid safety guar-

antees. Particularly, we use statistical tools from the conformal prediction literature [11, 12] to

obtain valid prediction regions that quantify the uncertainty of trajectory predictions. We then

formulate a model predictive controller (MPC) that incorporates trajectory predictions and valid

prediction regions. While our framework is compatible with any trajectory prediction algorithm,

we focus in the experiments on long short term memory (LSTM) networks [13–18] which are special

recurrent neural networks (RNN) that can capture nonlinear and long-term trends [19, 20]. Our

contributions are:

•We propose a planning algorithm that incorporates trajectory predictions and valid predic-

tion regions which are obtained using conformal prediction. The elegance in using conformal

prediction is that prediction regions are easy to obtain and tight. Our algorithm is com-

putationally tractable and, under reasonable assumptions, based on a convex optimization

problem.

•We provide valid safety guarantees which guarantee that the system is safe with a user-deﬁned

probability. Larger user-deﬁned probabilities naturally result in more conservative plans. The

strength of our approach is compatibility with state of the art trajectory predictors, e.g.,

RNNs and LSTMs, while making no assumptions on the underlying trajectory-generating

distribution.

•We provide numerical experiments of a mobile robot and a self-driving car using the Tra-

jNet++ toolbox [17] and the autonomous driving simulator CARLA [21].

1.1 Related Work

The works in [22–26] present non-interactive sampling-based motion planners, while [8, 27–29] pro-

pose non-interactive receding horizon planning algorithms that minimize the risk of collision. A

challenge in non-interactive methods is the robot freezing problem in which robots may come to a

deadlock due to too large prediction uncertainty [7], e.g., for long time horizons. While this problem

can be alleviated by receding horizon planning strategies, another direction to address this problem

is to model social interaction as in interactive approaches where typically an interaction model is

learned or constructed [9, 30–37]. Reinforcement learning approaches that take social interaction

into account were presented in [10, 38].

A particular challenge lies in selecting a good predictive model. Recent works have used intent-

driven models for human agents where model uncertainty was estimated using Bayesian inference

and then used for planning [39–41]. Other works considered Gaussian processes as a predictive

model [42–44]. To the best of our knowledge, none of the aforementioned works provide valid

safety guarantees unless strong assumptions are placed on the prediction algorithm and the agent

model or its distribution, e.g., being Gaussian.

We focus instead on the predictive strength of neural networks. Particularly, RNNs and LSTMs

have shown to be applicable to time-series forecasting [19, 20]. They were successfully applied

in domains such as speech/handwriting recognition and image classiﬁcation [45–48], but also in

trajectory prediction [13–18]. We will speciﬁcally use the social LSTM presented in [16] that can

jointly predict agent trajectories by taking social interaction into account.

Neural network predictors, however, provide no information about the uncertainty of a predic-

tion so that wrong predictions can lead to unsafe decisions. Therefore, monitors were constructed

in [49,50] to detect prediction failures – particularly [50] used conformal prediction to obtain guaran-

tees on the predictor’s false negative rate. Conformal prediction was also used to estimate reachable

sets via neural network predictors [51–53]. Conceptually closest to our work is [54] where a valid

predictor is constructed using conformal prediction, and then utilized to design a model predictive

controller. However, no safety guarantees for the planner can be provided as the predictor uses

a ﬁnite collection of training trajectories to represent all possible trajectories, implicitly requiring

training and test trajectories to be similar. Our approach directly predicts trajectories of the dy-

namic environment (e.g., using RNNs or LSTMs) along with valid prediction regions so that we

can provide end-to-end safety guarantees for our planner.

2 Problem Formulation

We ﬁrst deﬁne the safe planning problem in dynamic environments that we consider, and then

brieﬂy discuss methods for trajectory prediction of dynamic agents.

2.1 Safe Planning in Dynamic Environments

Consider the discrete-time dynamical system

xt+1 =f(xt, ut), x0:= ζ(1)

where xt∈ X ⊆ Rnand ut∈ U ⊆ Rmdenote the state and the control input at time t∈N∪ {0},

respectively. The sets Uand Xdenote the set of permissible control inputs and the workspace

of the system, respectively. The measurable function f:Rn×Rm→Rndescribes the system

dynamics and ζ∈Rnis the initial condition of the system.

The system operates in an environment with Ndynamic agents whose trajectories are a priori

unknown. Let Dbe an unknown distribution over agent trajectories and let

(Y0, Y1, . . .)∼ D

describe a random trajectory where the joint agent state Yt:= (Yt,1, . . . , Yt,N ) at time tis drawn

from RNn, i.e., Yt,j is the state of agent jat time t.1We assume at time tto have knowledge

of (Y0, . . . , Yt). Modeling dynamic agents by a distribution Dprovides great ﬂexibility, e.g., the

pedestrians in Fig. 1 can be described by distributions D1,D2, and D3with joint distribution D,

and Dcan generally describe the motion of Markov decision processes. We make no assumptions on

the form of the distribution D, but assume that Dis independent of the system in (1) as formalized

next.

Assumption 1. For any time t≥0, the control inputs (u0, . . . , ut−1)and the resulting trajectory

(x0, . . . , xt), following (1), do not change the distribution of (Y0, Y1, . . .)∼ D.

Assumption 1 approximately holds in many applications, e.g., a self-driving car taking conserva-

tive control actions that result in socially acceptable trajectories which do not change the behavior

of pedestrians. We later comment on ways to deal with distribution shifts in practice, and reserve

a thorough treatment of this issue for future papers. We further assume availability of training and

calibration data drawn from D.

Assumption 2. We have a dataset D:= {Y(1), . . . , Y (K)}in which each of the Ktrajectories

Y(i):= (Y(i)

0, Y (i)

1, . . .)is independently drawn from D, i.e., Y(i)∼ D.

Assumption 2 is not restrictive in practice, e.g., pedestrian data is available in autonomous

driving. Let us now deﬁne the problem that we aim to solve in this paper.

Problem 1. Given the system in (1), the random trajectory (Y0, Y1. . .)∼ D, a mission time T,

and a failure probability δ∈(0,1), design the control inputs utsuch that the Lipschitz continuous

constraint function c:Rn×RnN →Ris satisﬁed2with a probability of at least 1−δ, i.e., that

Pc(xt, Yt)≥0,∀t∈ {0, . . . , T }≥1−δ.

We note that the function ccan encode collision avoidance, but also objectives such as tracking

another agent. In our solution to Problem 1, we additionally achieve cost optimality in terms of a

cost function J(details below).

2.2 Trajectory Predictors for Dynamic Environments

Our goal is to predict future agent states (Yt+1, . . . , YT) from observations (Y0, . . . , Yt). Our pro-

posed planning algorithm is compatible with any trajectory prediction algorithm. Assume that

Predict is a measureable function that maps observations (Y0, . . . , Yt) to predictions ( ˆ

Yt+1|t,..., ˆ

YT|t)

of (Yt+1, . . . , YT). We now split the dataset Dinto training and calibration datasets Dtrain and Dcal,

respectively, and assume that Predict is learned from Dtrain.

A speciﬁc example of Predict are recurrent neural networks (RNNs) that have shown good

performance [20]. For τ≤t, the recurrent structure of an RNN is given as

τ:= H(Yτ, h1

τ−1),

τ:= H(Yτ, hi

τ−1, hi−1

τ),∀i∈ {2, . . . , d}

1For simplicity, we assume that the state of each dynamic agent is n-dimensional. This assumption can easily be

generalized.

2We assume that cis initially satisﬁed, i.e., that c(x0, Y0,0) ≥0.

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

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

10 玖币 0人已下载

立即下载

摘要：

SafePlanninginDynamicEnvironmentsusingConformalPredictionLarsLindemann∗1,MatthewCleaveland∗2,GihyunShim2,andGeorgeJ.Pappas21ThomasLordDepartmentofComputerScience,UniversityofSouthernCalifornia2DepartmentofElectricalandSystemsEngineering,UniversityofPennsylvaniaJune9,2023AbstractWeproposeaframeworkfo...

展开>> 收起<<

Safe Planning in Dynamic Environments using Conformal Prediction Lars Lindemann1 Matthew Cleaveland2 Gihyun Shim2 and George J. Pappas2.pdf

共18页,预览4页

还剩页未读，继续阅读

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

Safe Planning in Dynamic Environments using Conformal Prediction Lars Lindemann1 Matthew Cleaveland2 Gihyun Shim2 and George J. Pappas2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: