PaperlayerView exact revision on arXiv

Source-linked AI summary

A Random Finite Set Approach for Dynamic Occupancy Grid Maps with Real-Time Application

Dominik Nuss, Stephan Reuter, Markus Thom, Ting Yuan, Gunther Krehl, Michael Maile, Axel Gern, Klaus Dietmayer

arXiv:1605.02406v2cs.RO

TL;DR

Classical occupancy-grid methods assume stationary environments, while particle-based dynamic methods lack a rigorous multi-object state-estimation formulation. This paper models dynamic grid states as random finite sets and derives a particle-based PHD/MIB filter with a parallel real-time implementation. Experiments with real-world data show consistent estimation when process and observation models are appropriate, including useful velocity estimation and dynamic/static obstacle separation.

Abstract

from arXiv · show

Grid mapping is a well established approach for environment perception in robotic and automotive applications. Early work suggests estimating the occupancy state of each grid cell in a robot's environment using a Bayesian filter to recursively combine new measurements with the current posterior state estimate of each grid cell. This filter is often referred to as binary Bayes filter (BBF). A basic assumption of classical occupancy grid maps is a stationary environment. Recent publications describe bottom-up approaches using particles to represent the dynamic state of a grid cell and outline prediction-update recursions in a heuristic manner. This paper defines the state of multiple grid cells as a random finite set, which allows to model the environment as a stochastic, dynamic system with multiple obstacles, observed by a stochastic measurement system. It motivates an original filter called the probability hypothesis density / multi-instance Bernoulli (PHD/MIB) filter in a top-down manner. The paper presents a real-time application serving as a fusion layer for laser and radar sensor data and describes in detail a highly efficient parallel particle filter implementation. A quantitative evaluation shows that parameters of the stochastic process model affect the filter results as theoretically expected and that appropriate process and observation models provide consistent state estimation results.

I. INTRODUCTION

Classical grid maps estimate binary cell occupancy with Bayesian updates but assume stationary environments, limiting their treatment of moving road users. Prior dynamic approaches add motion through particles or expanded state grids, while this paper formulates dynamic grid mapping as an RFS problem and derives the PHD/MIB filter.

Classical grid mapping

  • Classical occupancy grids divide space into cells and recursively estimate each cell's binary free-or-occupied state with a Bayesian filter.The binary Bayes filter combines measurements over time under assumptions including independent measurements and an unchanging cell state.Source: §I · p. 1, A. Static Grid Mapping · p. 2

Motivation

  • Stationary-environment assumptions are unsuitable for vehicle perception because traffic includes moving vehicles and pedestrians.Grid maps remain useful for collision avoidance and sensor-data fusion because they represent free space and arbitrarily shaped objects.Source: §I · p. 1

Prior dynamic approaches

  • Existing dynamic approaches include joint mapping and tracking, particle-based grid representations, and four-dimensional Bayesian occupancy filters with explicit velocity states.The Bayesian occupancy filter models position and velocity but incurs high computational load because many cells are required.Source: §I · p. 1

Limitations of prior work

  • Particle-based dynamic grid maps reduce computational load but lack a stochastically rigorous multi-object state-estimation definition.Because particles can move between cells and jointly represent an unknown number of occupied cells, their meaning and initialization remain unclear.Source: §I · p. 1

Paper contribution

  • This paper models dynamic grid-cell states as random finite sets and derives the probability hypothesis density / multi-instance Bernoulli filter using FISST.The formulation gives filter parameters physical meaning and supports generic, stochastically rigorous filter design for multiple dynamic objects.Source: A. Contributions of this Paper · pp. 1–2
  • The paper realizes the PHD/MIB filter with particles, approximates it in the Dempster-Shafer domain, and develops a massively parallel real-time implementation.Its contributions include experiments with real-world data evaluating estimation error and consistency.Source: A. Contributions of this Paper · p. 2

1) State Representation:

Particle-based dynamic grid maps represent cell dynamics with particles, but prior methods lack a mathematically rigorous multi-object state definition. Random finite set theory supplies a framework for modeling uncertain object count and deriving principled multi-object Bayesian estimation.

State Representation

  • Prior methods interpret particles differently, using particle weight or additional free, static, and dynamic occupancy distributions to represent grid-cell state.These approaches commonly propagate particles under constant velocity and direction assumptions.Source: 1) State Representation · p. 3, 2) Prediction Step · p. 3
  • Particle-based filters lack a stochastic definition of the multi-object estimation problem, so particle meaning and weight normalization remain inconsistent.The literature describes evolutionary particle propagation rather than a fully defined Bayesian filter.Source: 3) Update Step · p. 3, C. Discussion · p. 4
  • Particle resampling eliminates low-weight particles, reproduces others, and assigns equal weights after resampling.This is used to avoid particle degeneration.Source: 4) Resampling · p. 3
  • Particle initialization is needed when measurements indicate occupancy without predicted particles, but prior work leaves the initialization detail and weight division unclear.New-particle weight should increase with measured occupancy and decrease with predicted occupancy, according to the stated heuristic intuition.Source: 5) Initialization · p. 3
  • Particles predicted from different cells jointly represent a group of objects rather than a specifically identified object.The number of occupied cells is itself random and must be estimated.Source: C. Discussion · p. 4
  • Random finite set theory models environments containing a random but limited number of objects and supports mathematically rigorous multi-object Bayesian filtering.Finite set statistics provide the basis for this formulation.Source: C. Discussion · p. 4, A. Multi-Object Bayes Filter · p. 4

B. PHD and Bernoulli RFS

The PHD and Bernoulli RFS provide complementary representations for dynamic grid mapping. The PHD summarizes multi-object state intensity, while Bernoulli components model cell-level existence and enable the PHD/MIB recursion.

B. PHD and Bernoulli RFS

  • The PHD is the first statistical moment of a multi-object density, and its integral gives the expected number of targets in an area.It can represent the posterior independently of whether particles or Gaussian mixtures are used.Source: B. PHD and Bernoulli RFS · p. 5, B. Multi-Object State Transition in… · p. 6
  • A Bernoulli RFS models whether one object exists with probability r and assigns its state the spatial PDF p(x).It assigns zero probability to sets containing two or more objects.Source: B. PHD and Bernoulli RFS · p. 5
  • The PHD/MIB filter combines PHD and Bernoulli filtering to recursively estimate dynamic grid-cell states and address object initialization and heterogeneous measurements.Its posterior is represented by a PHD, followed by cell-level Bernoulli processing.Source: §IV · p. 5, A. Environment Definition and Filter… · p. 5
  • The filter represents each real-world object with one or more point objects, with their count equal to the occupied grid cells.Point-object states can include position and velocity, with additional attributes allowed.Source: A. Environment Definition and Filter… · p. 5
  • PHD prediction propagates persistent point objects through a transition density, while new-born objects are handled in Bernoulli form.A constant-velocity model is one example of the transition process, with process noise and interval T.Source: B. Multi-Object State Transition in… · p. 6
  • The PHD/MIB approximation uses independent Bernoulli RFS instances for grid cells, each modeling occupancy, birth, and observation clutter.The PHD is transformed into cell-specific Bernoulli representations for subsequent processing.Source: C. Approximation as Bernoulli… · p. 6

D. Bernoulli RFS Birth Model

The PHD/MIB birth model follows Bernoulli filtering for new objects and adapts the observation process to measurement grids. Each cell allows at most one measurement with cell-specific detection and false-positive probabilities.

D. Bernoulli RFS Birth Model

  • The standard Bernoulli birth model assigns prior probability pB to a new object when no object exists and zero birth probability when an object already exists.The new object's spatial distribution is given by the birth PDF pb(xk+1).Source: D. Bernoulli RFS Birth Model · p. 6
  • The PHD/MIB filter uses the standard Bernoulli birth process and combines persistent and newborn objects into the predicted Bernoulli RFS.A simplifying equation assumes high persistence, pS ≈1.Source: D. Bernoulli RFS Birth Model · pp. 6–7
  • The predicted occupancy probability of a cell equals the combined existence probability of persistent or newborn point objects.This links cell occupancy to the Bernoulli representation.Source: D. Bernoulli RFS Birth Model · p. 7
  • Unlike Poisson clutter assumptions, the PHD/MIB observation model permits one measurement or no measurement per grid cell.This matches the stated practical structure of measurement grids.Source: E. Bernoulli Observation Process · p. 7
  • Occupied-cell measurements use true-positive probabilities, empty-cell measurements use false-positive probabilities, and false positives follow the clutter density pcl(z).Associated true positives use the single-object likelihood, while unassociated measurements use clutter density.Source: E. Bernoulli Observation Process · p. 7
  • The PHD/MIB observation update is performed independently for each grid cell using the cell's measurement and association quantities.The implementation receives cell-specific true-positive, false-positive, likelihood, and association information.Source: E. Bernoulli Observation Process · p. 7

F. Multi-Object Bayes Update Step

The PHD/MIB update represents each grid cell with a Bernoulli RFS and combines predicted states with measurement likelihoods. Under a deterministic static process model, it reduces to the generalized binary Bayes update.

V. PARTICLE REALIZATION OF THE PHD/MIB FILTER

The particle realization represents the PHD with weighted samples, propagates persistent and newly born objects, and processes each grid cell through independent Bernoulli instances. Birth probabilities are cell-specific design parameters.

E. Predicted Bernoulli RFS

The predicted Bernoulli RFS in each cell combines persistent and new-born particle sets, after which measurement updates adapt particle weights. The posterior cell existence probability is preserved through normalization and aggregation into a joint PHD.

  • Persistent and new-born particle sets together form the predicted Bernoulli RFS for each grid cell.Source: E. Predicted Bernoulli RFS · p. 9
  • The measurement-grid update adapts particle weights for each cell, using identical rules for persistent and new-born particles.Source: F. Particle Update · p. 9
  • When no measurement occurs in a cell, the filter applies a corresponding adapted-weight rule to both persistent and new-born particles.Source: F. Particle Update · p. 9
  • For multi-object distributions, normalized particle weights sum to the posterior existence probability rather than necessarily to one.Source: F. Particle Update · p. 9
  • The posterior occupancy probability of a cell is represented by the updated existence probability of a point object in that cell.Source: F. Particle Update · pp. 9–10
  • The posterior state of all point objects is represented by transforming the Bernoulli instances into a joint PHD.Source: G. Joint PHD Representation · p. 10
  • New-born particles can substantially increase state-estimation uncertainty, so their influence may be deferred until a later recursion.Source: G. Joint PHD Representation · p. 10
  • The filter resamples a constant number of particles from the joint posterior, with draw probabilities proportional to particle weights.Source: H. Resampling · p. 10

VI. REAL-TIME APPROXIMATION WITH DEMPSTER-SHAFER THEORY OF EVIDENCE

The DS-PHD/MIB filter approximates the particle-based PHD/MIB filter with Dempster-Shafer evidence to reduce particle requirements and support efficient implementation. It combines occupancy evidence with spatial likelihood and association information for cell updates.

  • The original particle realization may not be real-time capable in maps containing large unobserved areas.Source: §VI · p. 10
  • The DS-PHD/MIB filter uses Dempster-Shafer masses to avoid representing unobserved areas with particles.Source: §VI · p. 10
  • The DS-PHD/MIB approximation reduces the required number of particles and is easier to implement than the original particle-based filter.Source: §VI · p. 10
  • Each cell stores separate masses for occupied and free states within the frame of discernment {O, F}.Source: A. State Representation · p. 10
  • The filter represents occupied mass with particle-weight sums and obtains occupancy probability through the pignistic transformation.Source: A. State Representation · p. 10
  • Prediction propagates particles and separately models free-space evidence with a time-dependent discount factor.Source: B. Prediction · pp. 10–11
  • Unlike the formally derived PHD/MIB update, the DS-PHD/MIB update uses heuristic simplified equations designed to approximate it in the Dempster-Shafer domain.Source: C. Update · p. 11
  • Each measurement cell supplies an occupancy BBA, a spatial likelihood, and an association probability for the update.Source: C. Update · p. 11

2) Birth Model:

The DS-PHD/MIB birth-model update separates persistent and newly born objects, representing their posterior states with distinct particle sets and occupancy masses. Newborn particles are created and weighted according to measurement association and updated birth mass.

  • The DS-PHD/MIB filter splits occupied mass into persistent-object and newborn-object components.Source: 2) Birth Model · p. 11
  • Newborn particles are represented by separate particle sets for associated and unassociated spatial measurements.Source: 3) Spatial Update · p. 12
  • Persistent particles are updated by multiplying their weights with the spatial measurement likelihood and then normalizing them.Source: 3) Spatial Update · p. 12
  • Associated newborn particles are sampled from the state density conditioned on the measurement, whereas unassociated newborn particles are sampled from the birth distribution.Source: 3) Spatial Update · p. 12
  • Newborn particle sets are created only in grid cells whose measurement mass indicates occupancy, and their particle counts follow the corresponding occupancy masses.Source: 3) Spatial Update · p. 12
  • The posterior state combines the union of the particle sets with the grid cell’s posterior free mass.Source: 3) Spatial Update · p. 12

D. Resampling

The resampling and parallel implementation organize particles by predicted grid cell so occupancy updates and cell statistics remain efficient on massively parallel hardware. Sorting enables straightforward assignment and load-balanced accumulation.

B. Implementation Details

The implementation uses sorted particle and grid-cell arrays, parallel accumulation, and fixed-size particle storage to perform prediction, assignment, occupancy updates, particle updates, initialization, and moment computation efficiently.

Particle assignment

Grid-cell occupancy update

Persistent-particle update

Particle prediction

Particle initialization

Data structures

6) Statistical Moments of Grid Cells:

The implementation estimates grid-cell velocity moments from updated persistent particles using parallel accumulation. Experiments examine birth-probability effects, radar fusion, and real-time processing with laser and radar data.

6) Statistical Moments of Grid Cells:

Evaluation

  • The evaluation uses real-world laser and radar data to test velocity estimation, dynamic-static separation, and computation time.Source: §VIII · p. 16
  • The test vehicle uses a four-layer laser scanner and two short-range radars, with ego motion compensated from vehicle speed and yaw rate.Source: A. Experiment Configuration · p. 16
  • The grid map covers 120 m by 120 m with 10 cm cells, and the parallel implementation runs on an Nvidia GTX980 GPU with a single Intel i7 core.Source: A. Experiment Configuration · p. 16

Velocity estimation

C. Consistency of the DS-MIB/PHD filter

The evaluation examines how birth probability affects DS-PHD/MIB consistency, dynamic-cell classification, sensor fusion, and real-time computation. Appropriate stochastic modeling and parallel implementation produce consistent estimates and useful separation of dynamic and static obstacles.

Consistency under birth-probability variation

  • Increasing birth probability raises Segway velocity uncertainty because more newborn particles represent the dynamic object.The experiment measures the combined velocity variance of all grid cells representing the Segway.Source: C. Consistency of the DS-MIB/PHD filter · p. 17
  • A birth probability of pB = 0.005 can produce inconsistent estimates during acceleration maneuvers by underestimating uncertainty.The constant-velocity process model does not represent acceleration, so velocity process noise provides a trade-off between constant-velocity and acceleration behavior.Source: C. Consistency of the DS-MIB/PHD filter · p. 18

Separation of dynamic and static cells

  • A birth probability of pB = 0.02 achieves the best classification performance, with a 99% true positive rate at a 1% false positive rate.The classification uses Mahalanobis distance from the estimated velocity distribution to zero velocity.Source: D. Separation of Moving and Stationary… · p. 18

Sensor fusion

Overall evaluation

  • Real-world sensor-data experiments show consistent estimation with appropriate stochastic process and observation models and useful velocity estimation and obstacle separation.The DS-PHD/MIB formulation provides a mathematically rigorous random-finite-set approach, while the DS-PHD/MIB approximation supports real-time implementation.Source: §IX · p. 19

Related papers

Loading 1605.02406v2…