Motion Primitives Based Kinodynamic RRT for Autonomous Vehicle Navigation in Complex Environments Shubham Kedia1and Sambhu H. Karumanchi2

2025-05-02 0 0 2.15MB 7 页 10玖币

侵权投诉

Motion Primitives Based Kinodynamic RRT for Autonomous Vehicle

Navigation in Complex Environments

Shubham Kedia1and Sambhu H. Karumanchi2

Abstract— In this work, we have implemented a SLAM-

assisted navigation module for a real autonomous vehicle

with unknown dynamics. The navigation objective is to reach

a desired goal conﬁguration along a collision-free trajectory

while adhering to the dynamics of the system. Speciﬁcally,

we use LiDAR-based Hector SLAM for building the map of

the environment, detecting obstacles, and for tracking vehicle’s

conformance to the trajectory as it passes through various

states. For motion planning, we use rapidly exploring random

trees (RRTs) on a set of generated motion primitives to search

for dynamically feasible trajectory sequences and collision-free

path to the goal. We demonstrate complex maneuvers such as

parallel parking, perpendicular parking, and reversing motion

by the real vehicle in a constrained environment using the

presented approach. The demo videos are available HERE.

I. INTRODUCTION

Autonomous vehicles need reliable perception and robust

motion planning to perform complex maneuvers while avoid-

ing obstacles in their operating environment. Trajectories

generated by basic path planners that model only kinematics

are often non-executable in the real world because of the

limits on actuator forces and torques. Kinodynamic planning

[1], by design, integrates system dynamics constraints of the

form ˙x=f(x, u)in its modeling to guarantee collision-free

trajectories, where x∈Rnrepresents the vehicle state, and

u∈Rmthe control action. Kinodynamic path planning has

been actively researched for decades for robot navigation.

[2]–[5].

In real world, it is quite challenging to model the system

dynamics as an explicit mathematical function ˙x=f(x, u).

Especially, for autonomous vehicles the system identiﬁcation

is non-trivial due to the non-linearities in actuators and

vehicle systems. [6]–[8] explored high ﬁdelity autonomous

vehicle dynamics identiﬁcation. But their applicability for

real-time navigation tasks is limited due to high model

complexity.

Also, planning has to deal with the curse of dimensionality

because it entails search in a high dimension conﬁguration

space. The need for search over a high dimensional space

popularized the randomized sampling based Rapidly explor-

ing Randomized Trees (RRTs) [9] algorithm which, starting

with an initial vertex, incrementally constructs the tree by

repeatedly sampling a point in the conﬁguration space,

ﬁnding its nearest neighbor vertex in the existing tree, and

1Shubham Kedia is with the Department of Mechanical Science

and Engineering, University of Illinois at Urbana-Champaign, IL, USA

skedia4@illinois.edu

2Sambhu H Karumanchi is with the Department of Aerospace

Engineering, University of Illinois at Urbana-Champaign, IL, USA

shk9@illinois.edu

applying an allowable control that pulls the vertex towards

the random point. The latter feature biases the growth of

the tree towards unexplored space and returns a solution as

soon as the tree reaches the goal, a feature that makes the

algorithms suitable for a fast online implementation.

Fig. 1: Polaris GEM e2 autonomous vehicle

In this approach, a set of discrete control sequences called

motion primitives are used to extend the tree by appending

the node that is closest to the new sampled conﬁguration

at every step. We implement motion primitives based RRT

on a real autonomous vehicle and demonstrate complex

maneuvers like parallel parking, perpendicular parking, and

reversing in a constrained environment. The vehicle is Polaris

GEM e2 (Figure 1), a small, certiﬁed autonomous vehicle

housed at the Center for Autonomy at the University of Illi-

nois, Urbana-Champaign. We generate a ﬁxed set of motion

primitives (described in detail in Section 3) by performing

various different driving maneuvers on the autonomous car

to select a few simple, plausible maneuvers as our motion

primitives. The motion primitives based approaches have the

advantage that they can be so designed to directly encode

various basic motion behaviors depending on the application

and generate feasible trajectories with the help of sampling

algorithms like RRT. Refer to [10] for an interesting appli-

cation to the socially-aware robot navigation where socially-

guided primitives enact safe interaction between humans

and agents. Thus, motion primitives based RRT offers a

ﬂexible framework for autonomous vehicle motion planning

in diverse environments. In a vast majority of the works, the

arXiv:2210.11652v1 [cs.RO] 21 Oct 2022

use of RRTs in on-line planning systems for robotic vehicles

has been restricted to simulation, or to kinematics. As for

real-world implementations, MIT DARPA Urban Challenge

vehicle [11] used on-line RRT to deal with complex, unstable

dynamics and drift. In the same vein, our work reports a

more ﬂexible motion primitives based RRT on a real-world

autonomous car albeit in a laboratory environment.

The ease of autonomous vehicle navigation is tightly cou-

pled to reliable and accurate perception of its environment.

Our autonomous car uses LiDAR scans to perceive the

map of the environment and localizes itself within the map

using SLAM (Simultaneous Localization and Mapping). We

speciﬁcally use Hector SLAM [12] in our implementation

because of its ability to match with the high update rate

of LiDAR systems and provide accurate 2D pose estimates.

While Hector SLAM system does not aim at explicit loop

closing, it is known to generate sufﬁciently accurate mapping

in many settings [13]. In Section III, we describe the overall

methodology in detail.

II. RELATED WORKS

RRT [14] is a pioneering contribution in robot motion

planning which, along with its many important extensions,

found pervasive use in many robotic applications. Since it

will be hard to review all chronological contributions, we

will review some recent works pertaining only to autonomous

vehicles and urge the reader to refer to [15] for a compre-

hensive survey on RRT related works, and [16] and [17]

for a review of motion planning techniques for autonomous

vehicles, in general. [18] proposed a fast RRT algorithm

for autonomous road vehicles that uses off-line templates

of the trafﬁc scenes to assist in tree search. [19] invokes

desired orientation during the phase of tree expansion to

address navigation challenges in cluttered places like parking

lots. [20] focuses on autonomous navigation and collision

detection using a RRT-based dynamic path planning and a

path-following controller, and provides results in a simulated

environment. [21] proposes a sampling-based Closed-Loop

Rapidly exploring Random Tree (CL-RRT) for autonomous

heavy duty vehicles which often have second order differen-

tial constraints.

Authors Pivtoraiko et. al. [22] described motion primitives

based state lattice planner. The primitives are designed via

sampling in state spaces and are used to perform incremental

search using the D∗Lite [23] algorithm. [24] also explores

search based planning using state lattice and controller-based

motion primitives. However, these approaches are limited

to simulation and the proposed path planning cannot be

implemented on a real autonomous vehicle with unknown

dynamics. [25] and [26] are closest to our approach. [25]

discusses about path planning by concatenation of pre-

speciﬁed motion primitives and also studied graph-based

search techniques, where the graph does not represent a state

lattice but rather exhibits a tree structure. [26] presents in-

cremental search on a multi-resolution, dynamically feasible

lattice state space and includes experimental validation on

real autonomous vehicle but it employs an accurate vehicle

model.

In relation to the above works, our primary contributions

are as follows:

•The primary focus of our work is to depart from

simulated environment and demonstrate actual imple-

mentation of RRT-based motion planning and trajectory

tracking on a real autonomous vehicle.

•In contrast to the other RRT-based works, our approach

is designed to operate under unknown dynamics of

the vehicle. Moreover, our study is motion primitives-

centric that allows for encoding of application-speciﬁc

constraints such as actuator limits, for example, while

generating feasible trajectories.

•Our real-world experiments demonstrate the feasibility

of performing complex maneuvers like parallel parking,

perpendicular parking, and reversing the vehicle using

a single set of motion primitives within the RRT algo-

rithm.

III. METHODOLOGY

A. Mapping and Localization

To ﬁnd a collision-free trajectory from the start position

to the goal position, the autonomous car must create a map

of the environment and dynamically register its position as it

moves within the environment. Our autonomous car uses 2D

LiDAR scans to perceive the environment and localizes itself

using the Hector SLAM algorithm. For completeness, we

present here a few important computations involved in Hector

SLAM. Primarily, Hector SLAM uses an occupancy grid as

the map of the environment where each cell of the grid is

in one of the three states-occupied, free, or unexplored. A

LiDAR measurement is assigned 1,−1when the LiDAR hits

occlusion, or passes through the free space respectively. The

cells unexplored in the map by LiDAR are set to 0.

The problem of scan matching (matching the current scan

either with a previous scan or with an existing map) is to

ﬁnd the rigid transformation ξ= (px, py, θ)that minimizes

ξ∗=argmaxξ

i=1

[1 −M(Si(ξ)]2(1)

where Si(ξ)are the world coordinates of the endpoints of

scan i,si=si,x

si,y given by

Si(ξ) = cos(ψ)sin(−ψ)

sin(ψ)cos(ψ)si,x

si,y +px

py(2)

In the above, M(Si(ξ)) is the map value corresponding

to the point Si(ξ)). In terms of differential movement, the

above minimization problem can be transformed into ﬁnding

a change in pose ∆ξsuch that

i=1

[1 −M(Si(ξ+ ∆ξ)]2→0(3)

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

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

10 玖币 0人已下载

立即下载

摘要：

MotionPrimitivesBasedKinodynamicRRTforAutonomousVehicleNavigationinComplexEnvironmentsShubhamKedia1andSambhuH.Karumanchi2AbstractInthiswork,wehaveimplementedaSLAM-assistednavigationmoduleforarealautonomousvehiclewithunknowndynamics.Thenavigationobjectiveistoreachadesiredgoalcongurationalongacollis...

展开>> 收起<<

Motion Primitives Based Kinodynamic RRT for Autonomous Vehicle Navigation in Complex Environments Shubham Kedia1and Sambhu H. Karumanchi2.pdf

共7页,预览2页

还剩页未读，继续阅读

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

Motion Primitives Based Kinodynamic RRT for Autonomous Vehicle Navigation in Complex Environments Shubham Kedia1and Sambhu H. Karumanchi2

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: