Computing interval-valued coverage probability maps via Monte Carlo method and set-based evaluation

Esnault, Damien

doi:10.1016/j.ijar.2026.109764

Computing interval-valued coverage probability maps via Monte Carlo method and set-based evaluation

2026-07-01

0

PRE

AI

DOI：10.1016/j.ijar.2026.109764

Original

Original request for help

Save

Abstract

En 中文

This paper proposes a framework for constructing interval-valued coverage probability maps under stochastic vehicle dynamics and geometric set-evaluation indeterminacy. Classical Monte Carlo coverage estimation relies on binary inclusion tests that assume exact geometric evaluation: each spatial cell is declared either covered or uncovered for every trajectory realization. In practice, however, covered regions are computed numerically and may only be available through finite-resolution set approximations, leading to partial coverage or unresolved inclusion cases. To address this issue, we introduce a three-valued inclusion test that distinguishes certified full coverage, certified non-coverage, and indeterminate outcomes. This logic is embedded into an interval-valued Monte Carlo estimator by defining lower and upper interpretations of indeterminate cases. The resulting empirical interval-valued estimator converges almost surely, as the number of samples increases, to a deterministic probability interval enclosing the true cell coverage probability. For each trajectory realization, the covered region is evaluated using certified set-based computations based on separators and a branch-and-contract paving algorithm, which provide inner and outer approximations required for the three-valued cell evaluation. The resulting interval estimates are assembled into coverage probability maps over spatial cells, and an adaptive probability-driven refinement strategy refines the final map according to an interval-width criterion. Numerical simulations with a stochastic Dubins-type underwater vehicle illustrate the approach and highlight the trade-off between geometric resolution, computational effort, and interval-valued uncertainty representation.

Keywords:

Interval-valued probabilities

Coverage probability maps

Monte Carlo methods

Three-valued logic

Guaranteed set computations

Branch-and-contract

Underwater robotics

Computing interval-valued coverage probability maps via Monte Carlo method and set-based evaluation

Abstract

Journal

Organization

Cited Papers