.png){kind=icon}
.png){kind=icon}
Return
Navigation reliability assessment on occupancy grid networks for AMR navigation using a dynamic programming binary-addition-tree algorithm
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ress.2026.113214.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Autonomous mobile robots (AMRs) require reliability-aware navigation because classical shortest-path planners do not quantify traversal success under uncertain occupancy. This paper proposes DP-BAT, an exact model-specific navigation-reliability method for Occupancy Grid Networks (OGNs). DP-BAT evaluates reliability within a selected δ-corridor around a reference path under a monotone block-ordered navigation constraint and an independent-cell probabilistic model by combining ordered block decomposition, block-based Binary-Addition-Tree (BAT) enumeration, and dynamic programming (DP) probability propagation. To reduce redundant states without altering the exact reliability value, three admissible state-reduction rules are introduced: the 0-vector rule, the 1-vector rule, and the Gateway-Zero Cut Rule. The last of these removes certified zero-gate configurations during constrained BAT generation, before the DP reachability checks are performed. DP-BAT is compared with QuickBAT, Monte Carlo Simulation (MCS), and a frontier-based Binary Decision Diagram (BDD) under the same adopted corridor model. On random grids up to 1000 × 1000, DP-BAT preserves exact reliability under this model while requiring 27.6 ms at 1000 × 1000, compared with 21,450.3 ms for MCS with 105 runs. For random corridors with obstacle rate 45% and δ = 1, DP-BAT is faster than BDD in all tested sizes from 5 × 5 to 100 × 100, including 3.969 ms versus 7.105 ms at 100 × 100. Structured-map experiments on Willow Garage, Intel Research Lab, FR079, and Orebro show the same block-size dependence: DP-BAT completed Willow Garage and Intel in 1936.956 ms and 26,277.526 ms while BDD timed out; on FR079, DP-BAT required 5.959 ms versus 32.479 ms for BDD; on Orebro, both exact methods timed out. These results show that DP-BAT is effective when the δ-corridor yields small local blocks.
Keywords:
Autonomous mobile robot (AMR)
Navigation reliability
Occupancy grid network (OGN)
Dynamic programming (DP)
Binary-addition-tree (BAT)
Binary decision diagram (BDD)
Monte Carlo simulation (MCS)
Gateway-zero cut rule
Journal
R
IF:
11
Papers:
813
Citations:
0