Organizations: School of Automation and Intelligent Sensing, Shanghai Jiao Tong University and Institute of Medical Robotics, Shanghai Jiao Tong University, Shanghai 200240, China. · Key Laboratory of System Control and Information Processing, Ministry of Education of China, and Shanghai Engineering Research Center of Intelligent Control and Management, Shanghai 200240, China.
Uncertainties arising from localization error, trajectory prediction errors of the moving obstacles and environmental disturbances pose significant challenges to robot's safe navigation. Existing uncertainty-aware planners often approximate polygon-shaped robots and obstacles using simple geometric primitives such as circles or ellipses. Though computationally convenient, these approximations substantially shrink the feasible space, leading to overly conservative trajectories and even planning failure in narrow environments. In addition, many such methods rely on specific assumptions about noise distributions, which may not hold in practice and thus limit their performance guarantees. To address these limitations, we extend the Optimization-Based Collision Avoidance (OBCA) framework to an uncertainty-aware formulation, termed U-OBCA. The proposed method explicitly accounts for the collision risk between polygon-shaped robots and obstacles by formulating OBCA-based chance constraints, and hence avoiding geometric simplifications and reducing unnecessary conservatism. These probabilistic constraints are further tightened into deterministic nonlinear constraints under mild distributional assumptions, which can be solved efficiently by standard numerical optimization solvers. The proposed approach is validated through theoretical analysis, numerical simulations and real-world experiments. The results demonstrate that U-OBCA significantly mitigates the conservatism in trajectory planning and achieves higher navigation efficiency compared to existing baseline methods, particularly in narrow and cluttered environments.
Figures & tables
Fig. 1: Motivation: collision risk assessment between polygonal shapes under pose uncertainty.
Fig. 2: The distance between the vehicle and the obstacle.
Fig. 3: The simulation results in the parallel parking scenario.
Methods
Cost
Collision Num
Success Rate
U-OBCA (α=0.01)
37.18
32
97.1%
U-OBCA (α=0.1)
10.54
178
87.0%
OBCA [ 21 ]
10.32
3210
1.4%
TABLE I: Simulation results comparison of different methods in parking scenario
Methods
Success Rate (%)
Finishing Time (s)
Mean Cost Value
Min Distance (m)
Mean Computation Time (s)
U-OBCA
97
11.887 ± 0.956
197.423 ± 49.518
0.174 ± 0.069
0.114 ± 0.071
OBCA [ 21 ]
35
11.679 ± 0.839
181.757 ± 41.100
0.043 ± 0.045
0.109 ± 0.049
RCA [ 2 ]
84
13.446 ± 2.994
232.375 ± 85.929
0.558 ± 0.503
0.066 ± 0.044
LCC [ 6 ]
82
13.338 ± 3.061
232.247 ± 109.238
0.316 ± 0.177
0.089 ± 0.059
ECC [ 7 ]
82
13.616 ± 3.212
246.505 ± 110.087
0.561 ± 0.251
0.085 ± 0.063
RC [ 10 ]
84
12.884 ± 2.966
226.178 ± 99.326
0.367 ± 0.114
0.088 ± 0.138
TABLE II: Simulation result comparison of the different methods in random corridor scenarios
Fig. 4: The simulation results in the narrow corridor scenario.
Fig. 5: The smart wheelchair platform.
Fig. 6: Software architecture of the experimental platform.
Fig. 7: Detection and trajectory prediction results using the algorithm in [ 33 ] .
Expectation
Variance
x
−5.27×10−3m
7.28×10−4m2
y
−3.22×10−3m
3.17×10−4m2
θ
3.70×10−2deg
5.89×10−2deg2
TABLE III: Estimated expectation and variance of the smart wheelchair’s localization error
Variance
Pose 1
Pose 2
Pose 3
Pose 4
Pose 5
Pose 6
Pose 7
Pose 8
Round obstacle x ( ×10−4m2 )
10.37
8.75
9.38
11.33
11.05
9.29
8.93
10.02
Round obstacle y ( ×10−4m2 )
5.22
4.70
4.23
4.78
4.95
4.44
4.02
4.68
Polygon obstacle x ( ×10−4m2 )
15.85
13.21
11.03
13.68
14.45
13.89
14.58
16.67
Polygon obstacle y ( ×10−4m2 )
4.07
4.19
4.22
4.72
5.11
4.80
5.02
5.78
Polygon obstacle θ ( ×10−2deg2 )
10.22
8.31
11.67
10.38
15.92
11.28
9.73
10.69
TABLE IV: Estimated variances of static obstacle pose perception error
Fig. 8: An example of predicted pose error for a polygon-shaped obstacle at pose 3.
Variance
Pose 1
Pose 2
Pose 3
Pose 4
x (Round) ( ×k×10−4m2 )
6.72
6.37
5.63
5.45
y (Round) ( ×k×10−4m2 )
8.28
9.17
8.35
8.97
x (Polygon) ( ×k×10−4m2 )
6.92
6.60
6.54
7.20
y (Polygon) ( ×k×10−4m2 )
12.32
11.64
9.58
10.62
θ (Polygon) ( ×10−2deg2 )
10.17
8.37
9.52
9.21
TABLE V: Estimated variances of moving obstacle predicted pose error
Fig. 9: The experiment scenario of narrow corridor.
Fig. 10: Comparison of the navigation finishing time and the minium distance to obstacles between methods.
Fig. 11: The experiment scenario of the parking experiment.
Methods
Finishing Time (s)
Mean Cost
Mean Computation Time (ms)
Mean Distance (m)
Min Distance (m)
U-OBCA
32.44
267.08
557.98
1.37
0.30
RCA [ 2 ]
42.23
324.32
427.75
1.73
0.69
LCC [ 6 ]
42.16
337.09
435.62
1.70
0.69
ECC [ 7 ]
40.33
302.67
467.88
1.72
0.68
RC [ 10 ]
40.43
311.16
493.28
1.95
0.72
DRCC [ 17 ]
40.35
296.08
478.02
1.83
0.67
TABLE VI: Comparison of different methods in real world narrow corridor navigation scenarios
Finishing Time (s)
Mean Computation Time (ms)
Min distance (m)
7.96
400.13
0.17
TABLE VII: U-OBCA experiment results in real world parking scenarios
Department of Electrical Engineering and Computer University of Houston Houston, TX 77004, USA · Department of Engineering Technology University of Houston Houston, TX 77004, USA