Quadratic approximation based heuristic for optimization-based coordination of automated vehicles in conﬁned areas Stefan Kojchev1 Robert Hult2and Jonas Fredriksson3

2025-05-02 0 0 872.43KB 7 页 10玖币

侵权投诉

Quadratic approximation based heuristic for optimization-based

coordination of automated vehicles in conﬁned areas

Stefan Kojchev1, Robert Hult2and Jonas Fredriksson3

Abstract— We investigate the problem of coordinating mul-

tiple automated vehicles (AVs) in conﬁned areas. This problem

can be formulated as an optimal control problem (OCP) where

the motion of the AVs is optimized such that collisions are

avoided in cross-intersections, merge crossings, and narrow

roads. The problem is combinatorial and solving it to optimality

is prohibitively difﬁcult for all but trivial instances. For this

reason, we propose a heuristic method to obtain approximate

solutions. The heuristic comprises two stages: In the ﬁrst

stage, a Mixed Integer Quadratic Program (MIQP), similar in

construction to the Quadratic Programming (QP) sub-problems

in Sequential Quadratic Programming (SQP), is solved for the

combinatorial part of the solution. In the second stage, the

combinatorial part of the solution is held ﬁxed, and the optimal

state and control trajectories for the vehicles are obtained by

solving a Nonlinear Program (NLP). The performance of the

algorithm is demonstrated by a simulation of a non-trivial

problem instance.

I. INTRODUCTION

The idea of fully automated vehicles (AV) is receiving

substantial attention from both the public and scientiﬁc world

as signiﬁcant progress towards deploying automated vehicles

has been made during the last decade. Unfortunately, many

barriers between the current state-of-the-art and large-scale

commercial application exits, especially for deployment of

automated vehicles on public roads [1]. However, in conﬁned

areas, such as ports, mines, and logistic centers, some of

the hard challenges of public road driving are absent. In

particular, such areas are typically void of unpredictable

non-controlled actors, which dramatically reduces safety

concerns. Therefore, it is believed that conﬁned areas present

a good opportunity for early, large-scale deployment of

automated vehicles, as part of larger commercial transport

solutions for material ﬂow.

One of the challenges in conﬁned areas is the safe and ef-

ﬁcient coordination of AVs in mutually exclusive (MUTEX)

zones, such as intersections, work-stations (e.g. crushers,

loading/unloading spots, etc.), narrow roads, and, in the case

of electriﬁed AVs, charging-stations. Adequate coordination

can lead to improved energy-efﬁciency and considerable

increases in productivity.

*This work is partially funded by Sweden’s innovation agency Vinnova,

project number: 2018-02708.

1Stefan Kojchev is with Volvo Autonomous Solutions and the Mecha-

tronics Group, Systems and Control, Chalmers University of Technology

stefan.kojchev@volvo.com;kojchev@chalmers.se

2Robert Hult is with Volvo Autonomous Solutions, 41873 G¨

oteborg,

Sweden robert.hult@volvo.com

3Jonas Fredriksson is with the Mechatronics Group, Systems and

Control, Chalmers University of Technology, 41296 G¨

oteborg, Sweden

jonas.fredriksson@chalmers.se

A. Related Work

Automating and coordinating intersections for fully au-

tomated vehicles is a frequently discussed control problem,

see [2] for a comprehensive survey. The problem has been

formally shown to be NP-hard [3], and such problems are

in general difﬁcult to solve. For this reason a number of

methods have been proposed, leveraging results from, e.g.,

solutions based on hybrid system theory [4], reinforcement

learning [5], scheduling [6], model predictive control (MPC)

[7], [8] or direct optimal control (DOC) [9], [10].

In contrast to intersection scenarios often found in the

literature, conﬁned areas have a number of distinguishing

features. For example, in the case of intersection coordina-

tion, an approach that is often considered is to have vehicles

arriving at speed in a cutout around the intersection area

[7], [8]. This is often motivated by practical considerations;

neither the intent of the automated vehicles nor the state

of the uncertain environment can be accurately predicted

over long time-horizons. For conﬁned areas, however, it is

possible, and desirable, to plan the motion of each vehicle

from the start of a transport mission to its end. Moreover,

a number of works on public-road applications focus on

distributed and decentralized schemes, sometimes with inter-

mittent or corrupted communication [17]. For applications at

conﬁned sites, a central computational unit and good wireless

coverage can often be assumed. Thus, for these use cases,

we believe that a centralized approach that provides high

level control actions is favorable. A low level controller that

tracks the obtained optimal state and control trajectories will

typically be also deployed in practice, however, it is not

covered in this work.

B. Main Contribution and Outline

In this paper, we formulate the site-coordination problem

as an optimal control problem, which after transcription

results in a Mixed Integer Nonlinear Program, and propose a

two-staged heuristic method for its approximate solution. In

the ﬁrst stage of the heuristic, an MIQP problem is solved to

obtain the combinatorial part of the solution, i.e., the order in

which the vehicles utilize the MUTEX-zones. In the second

stage, the combinatorial part is ﬁxed and a continuous NLP

is solved for the optimal vehicle trajectories. The MIQP

of the ﬁrst stage is formed as an approximation of the

original MINLP, in a manner similar to how the Quadratic

Programming (QP) sub-problems are formed in Sequential

Quadratic Programming (SQP) [11]. The idea of using SQP-

like methods in approximate solution of MINLPs has been

used in other works [13], [14], however, to the authors’ best

arXiv:2210.14911v1 [math.OC] 26 Oct 2022

Fig. 1. Types of conﬂict zones.

knowledge, it has not been adapted and applied to vehicle

coordination problems. A structurally similar heuristic was

presented in [9], where a scheduling problem is derived

from the original MINLP, with the introduction of a number

of approximations, and solved as an MIQP. While sharing

the same two-staged structure, the method presented in this

paper avoids some of the approximations and shortcom-

ings of [9], without expanding the combinatorial solution

space. In particular, the heuristic presented herein enables

easy inclusion of rear-end collision constraints, which were

previously neglected, and avoids the expensive computation

of parametric sensitivities.

In addition to the cross-intersections, we consider merge-

split and narrow road MUTEX zones. In the merge-split

MUTEX zones, the vehicles ﬁrst join in on a common

patch of road which after some distance separate, and in

the narrow-roads the vehicles that are coming from different

directions join in on a common patch of road. Merge-split

and narrow roads are often found in conﬁned sites and occur

due to the construction of the site. Although the approach

focuses on conﬁned sites, the method of handling the mutual

exclusion zones can be extendable to other scenarios as well

(e.g., public road applications).

The remainder of the paper is organized as follows:

Section II presents a formulation of the problem that is solved

in this paper. In Section III the method for solving the stated

problem is presented, followed by Section IV where simula-

tion results illustrate the coordination algorithm. Section V

concludes the work and provides some possible extensions.

II. PROBLEM FORMULATION

In this paper, we consider a fully conﬁned area, meaning

that non-controlled trafﬁc participants such as pedestrians,

manually operated vehicles, bicycles, etc., are absent. Fur-

thermore, the conﬁned road network consists of Nafully

automated vehicles with cross-intersection, path merges, path

splits, and narrow roads. In addition, we assume that the

paths of all vehicles, i.e., their routes through the road

network are known, that overtakes are prohibited, and that

no vehicle reverses.

A. Optimal Coordination Problem

The problem of ﬁnding the optimal vehicle trajectories that

avoid collisions can be stated as:

Problem 1: (Optimal coordination problem) Obtain the

optimal state and control trajectories X∗=x∗

1, ..., x∗

Na,

U∗=u∗

1, ..., u∗

Na, given the initial state X0=

{x1,0, ..., xNa,0}, by solving the optimization problem

min

xi,ui,OI,OM

i=1

Ji(xi, ui)(1a)

s.t initial states xi,0= ˆxi,0,∀i(1b)

system dynamics ∀i(1c)

state and input constraints ∀i(1d)

safety constraints ∀i(1e)

where Nais the number of vehicles, Ji(xi, ui)is the cost

function, OI,OMare the order in which the vehicles enter

the MUTEX zones and will be formally stated in this section.

The problem is formulated in the spatial domain as it is

beneﬁcial to optimize the trajectories of the vehicles over

their full paths. The rationale for using spatial dynamics is

that the time it takes for the vehicle to traverse a path is not

known a-priori. Thus, it is inappropriate to plan the vehicle’s

motion with time as the independent variable.

B. System dynamics and state and input constraints

The system dynamics for vehicle i∈1, ..., Nain the

spatial domain can be formed using that dpi

dt=vi(t)and

dt= dpi/vi(t)and stated as

dti

dpi

vi(pi)(2)

dxi

dpi

vi(pi)fi(pi, xi(pi), ui(pi)) (3)

0≤h(pi, xi, ui).(4)

where the position piis the independent variable, the time ti

and xiare the vehicle state variables, where xi∈Rn−1

collects the remaining vehicle states, and ui∈Rmthe

control input, with i∈ {1, . . . , Na}. Note that what the

remaining state variable (xi) are, depends on what model is

used for the system dynamics. We assume that the functions

fiand hi, that describe the vehicle system’s dynamics and

constraints, are smooth.

C. Safety constraints

The safety constraints should ensure a collision-free cross-

ing of the conﬂict zone (CZ) that the vehicles encounter.

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

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

10 玖币 0人已下载

立即下载

摘要：

Quadraticapproximationbasedheuristicforoptimization-basedcoordinationofautomatedvehiclesinconnedareasStefanKojchev1,RobertHult2andJonasFredriksson3AbstractWeinvestigatetheproblemofcoordinatingmul-tipleautomatedvehicles(AVs)inconnedareas.Thisproblemcanbeformulatedasanoptimalcontrolproblem(OCP)wher...

展开>> 收起<<

Quadratic approximation based heuristic for optimization-based coordination of automated vehicles in conﬁned areas Stefan Kojchev1 Robert Hult2and Jonas Fredriksson3.pdf

共7页,预览2页

还剩页未读，继续阅读

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

Quadratic approximation based heuristic for optimization-based coordination of automated vehicles in conﬁned areas Stefan Kojchev1 Robert Hult2and Jonas Fredriksson3

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: