Safe Path Planning for Polynomial Shape Obstacles via Control Barrier Functions and Logistic Regression Chengyang Peng1 Octavian Donca1 and Ayonga Hereid1

2025-05-03 0 0 3.12MB 7 页 10玖币

侵权投诉

Safe Path Planning for Polynomial Shape Obstacles via Control Barrier

Functions and Logistic Regression

Chengyang Peng1, Octavian Donca1, and Ayonga Hereid1

Abstract— Safe path planning is critical for bipedal robots to

operate in safety-critical environments. Common path planning

algorithms, such as RRT or RRT*, typically use geometric or

kinematic collision check algorithms to ensure collision-free

paths toward the target position. However, such approaches

may generate non-smooth paths that do not comply with the

dynamics constraints of walking robots. It has been shown

that the control barrier function (CBF) can be integrated

with RRT/RRT* to synthesize dynamically feasible collision-free

paths. Yet, existing work has been limited to simple circular or

elliptical shape obstacles due to the challenging nature of con-

structing appropriate barrier functions to represent irregular-

shaped obstacles. In this paper, we present a CBF-based RRT*

algorithm for bipedal robots to generate a collision-free path

through complex space with polynomial-shaped obstacles. In

particular, we used logistic regression to construct polynomial

barrier functions from a grid map of the environment to

represent arbitrarily shaped obstacles. Moreover, we developed

a multi-step CBF steering controller to ensure the efﬁciency

of free space exploration. The proposed approach was ﬁrst

validated in simulation for a differential drive model, and then

experimentally evaluated with a 3D humanoid robot, Digit, in

a lab setting with randomly placed obstacles.

I. INTRODUCTION

Mobile robots have shown encouraging promises in many

real-world applications outside traditional well-structured

factory settings thanks to the recent advancement of real-

time path planning [1]. Path planning has been extensively

studied over the past decades [2], [3]. A feasible path for

a robot requires starting from an initial position to the

goal position without colliding with any obstacle in the

environment. Arguably the most prevailing approach in path

planning is the sampling-based Rapidly Exploring Random

Trees (RRT) algorithm, which expends the path by randomly

sampling points in the conﬁguration space [4]. To improve

the optimality of the resulting path, Karaman and Frazzoli [5]

proposed RRT*, which can reconnect the newly added node

to the nearby nodes based on the minimum cost from the

root node to the new node. Much progress has been made

recently in combining low-level control synthesis and path

planning, such as LQR-RRT* [6], [7], to ensure that the

generated paths are consistent with the underlying dynamics

constraints of the robot.

With the trending occasions of robots operating in

the safety-critical environment (e.g., around people or in

crowded spaces), the safety of robot motion becomes in-

creasingly critical for the continuous deployment of these

*This work was supported in part by the National Science Foundation

under grant FRR-21441568.

1Mechanical and Aerospace Engineering, Ohio State University, Colum-

bus, OH, USA. (peng.947, donca.2, hereid.1)@osu.edu.

Fig. 1. The snapshots of the bipedal robot, Digit, following

the collision-free path generated by the proposed algorithm.

intelligent machines. Control Barrier Function, a popular

tool in guaranteeing safety for nonlinear systems and con-

straints [8], has been shown effective in enforcing the safety-

critical constraints on nonlinear systems such as autonomous

vehicles and bipedal robot locomotion [9], [10]. Recently,

this method has also been used for designing safety-critical

path planners. Yang et al. introduced a Quadratic Program

(QP) that enforces Control Barrier Function (CBF) con-

straints to achieve obstacle avoidance [11]. Aniketh et al.

proposed a framework to incorporate CBF constraints into

the RRT path planning [12]. On these foundations, Ahmad

et al. also combined RRT* algorithm with the CBF and

equipped it with an adaptive sampling method to improve

the efﬁciency [13]. However, these obstacles studied by these

algorithms only focused on circular and elliptical shapes

because it would be easy to obtain their barrier functions.

In many real-world scenarios, the circular barrier function is

insufﬁcient or wasteful to represent complex-shaped obstacle

regions.

In this work, we developed a modiﬁed CBF-RRT* algo-

rithm with a new CBF-QP based multi-step steering con-

troller for safe path planning in complex environments. The

contributions of the proposed work are as follows. First,

we proposed a new method that uses logistic regression

to construct barrier functions that use polygon shapes to

represent complex obstacles. Second, instead of calculating

CBF-QP once when sampling a new node and moving one

step, we would divide one step into four small steps and

calculate them each, which can effectively keep the robot

safe (avoiding collision). Finally, we applied our modiﬁed

CBF-RRT* algorithm to bipedal robots to enable the robot

arXiv:2210.03704v1 [cs.RO] 7 Oct 2022

to navigate safely in a room with complex obstacles and

unreachable regions. We evaluated the proposed algorithm

on a Digit robot in the lab setting and demonstrated safe

navigation of bipedal walking robots.

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

reviews the background of the control barrier function (CBF)

and its integration with RRT/RRT* based planning algo-

rithms. In Section III, we presents the core contribution

of the paper, a CBF-RRT* planning algorithm with multi-

step steering and polynomial-shaped barrier representation

of complex obstacles. The simulation and experimental re-

sults with Digit robot are presented in Section IV. Finally,

Section Vbrieﬂy discusses the limitation of the proposed

work and future research directions.

II. BACKGROUND

In this section, we brieﬂy review the mathematical basis

of the control barrier function (CBF) and how it has been

integrated with the RRT/RRT* based planning algorithms for

safe navigation.

A. Control Barrier Function (CBF)

We consider the robot dynamics can be written as the

following afﬁne nonlinear system:

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

where x∈ X is the system state with X ⊆ Rnbeing the state

space, and u∈ U is the control input with U ⊆ Rmbeing the

control space. If there exists a continuous and differentiable

function h:Rn→R, the safety set Cof the system can be

deﬁned as [14]:

C={x∈Rn|h(x)≥0},

∂C={x∈Rn|h(x)=0},

Int(C) = {x∈Rn|h(x)>0}.

(2)

If h(x)has relative degree m > 1, we can deﬁne a serious

function ψm(x) : Rn→Rgiven as [15]:

ψ0(x) = h(x)m= 0,

ψm(x) = ˙

ψm−1(x) + αm(ψm−1(x)) m≥1,(3)

where αm(·)is a class κfunction. The forward invariance

safety condition can then be guaranteed if the following

inequality constraints are satisﬁed for all x∈ C:

fh(x) + LgLm−1

fh(x)u+∂mh(x)

∂tm+O(h(x))

+αm(ψm−1(x)) ≥0,(4)

where O(h(x)) denotes the remaining Lie derivatives along

fand partial derivatives with respect to twith degree less

than or equal to m−1. Therefore, if h(x)satisﬁed both (2)

and (4), it can be called a control barrier function. Since the

control input uis afﬁne in (4), one can formulate a quadratic

programming (QP) controller subject to the CBF constraint

in (4) to synthesize safe control actions [9], [14], [15].

B. CBF-RRT/RRT*

Built upon the standard RRT algorithm, Yang et al. de-

veloped the CBF-RRT path planning algorithm that uses

CBF-QP [9] based safety-critical controllers to generate

intermediate control actions to steer the robot away from the

obstacles when approaching them [11]. The CBF controller

replaces the collision check function in the traditional RRT

algorithm while still ensuring safety. In [12], Aniketh et al.

improved the computational efﬁciency of CBF-RRT further

by replacing CBF-QP with a random sampling of control

actions that satisfy the barrier condition described in (4).

While it preserves the nature of random exploration by

RRT, these approaches are often unable to generate (prob-

abilistically) optimal paths. To improve the optimality of

the resulting path, Ahmad et al. combined CBF-QP with

RRT* based on the work in [11], and improved the sampling

efﬁciency through adaptive sampling based on the cross-

entropy method (CEM) [13]. It has been shown that RRT*

yields a relatively optimal solution if given sufﬁcient compu-

tation time. This is realized through two critical procedures

described below [16]:

•ChooseParent: ﬁnds the near neighbor nodes around

the new node. If there is no obstacle collision between

the new node and each near node, algorithm will

compute the cost of the new node through each near

node. Finally, it chooses the neighbor node that makes

the cost minimum, as the parent node of the new node.

•Rewrite: reconnects each near neighbor node with

the new node and check their collisions. Calculates the

costs of these near nodes through the new node. Finally,

it selects the optimal cost and rewrites the tree.

In [13], the authors replaced the collision check function

in the above two procedures with a CBF-QP based steer-

ing function, which inevitably increased the computational

overhead of the CBF-RRT*. It is also important to note

that the three aforementioned studies expand the tree by

randomly sampling a note on the tree to extend toward the

target position. This practice is inefﬁcient in expanding the

tree outward into feasible areas, thereby increasing the total

number of iterations, as well as the computation overhead,

required for the algorithm. Moreover, determining a proper

set of barrier functions to describe obstacles and unreachable

areas remains challenging when using CBF for sampling-

based path planning. The existing work only considers simple

shapes, such as circles or ellipses.

III. SAFE NAVIGATION VIA MULTI-STEP CBF-QP

STEERING WITH RRT*

In this section, we present a safe path planning algorithm

for bipedal robots that integrates the control barrier func-

tion with RRT* to provide guaranteed obstacle avoidance

without explicit collision checking. Moreover, we propose to

construct polynomial barrier functions to represent complex

obstacles or unreachable regions using logistic regression on

the planar grid map of the environment. Finally, we develop a

multi-step CBF steering algorithm to address the infeasibility

issues that the state may end up in the unsafe set.

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

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

10 玖币 0人已下载

立即下载

摘要：

SafePathPlanningforPolynomialShapeObstaclesviaControlBarrierFunctionsandLogisticRegressionChengyangPeng1,OctavianDonca1,andAyongaHereid1AbstractSafepathplanningiscriticalforbipedalrobotstooperateinsafety-criticalenvironments.Commonpathplanningalgorithms,suchasRRTorRRT*,typicallyusegeometricorkinema...

展开>> 收起<<

Safe Path Planning for Polynomial Shape Obstacles via Control Barrier Functions and Logistic Regression Chengyang Peng1 Octavian Donca1 and Ayonga Hereid1.pdf

共7页,预览2页

还剩页未读，继续阅读

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

Safe Path Planning for Polynomial Shape Obstacles via Control Barrier Functions and Logistic Regression Chengyang Peng1 Octavian Donca1 and Ayonga Hereid1

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: