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.

  • Problem

    Classical grid maps assume stationary environments, while prior particle-based dynamic maps lack a stochastically rigorous definition of the multi-object estimation problem.

  • Method

    The paper formulates dynamic grid-cell estimation as a random finite set problem and derives a particle-based probability hypothesis density / multi-instance Bernoulli filter.

  • Results

    Appropriate stochastic process and observation models produced consistent estimation results, with useful velocity estimation and separation of dynamic from static obstacles.

  • Takeaways & Limitations

    The RFS formulation gives filter parameters physical meaning and supports real-time dynamic grid mapping with laser and radar sensor data.

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.
  • 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.
  • 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.
  • 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.
  • 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.
  • Paper contribution: 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.

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.
  • State Representation: 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.
  • State Representation: Particle resampling eliminates low-weight particles, reproduces others, and assigns equal weights after resampling.This is used to avoid particle degeneration.
  • State Representation: 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.
  • State Representation: 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.
  • State Representation: 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.

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.
  • B. PHD and Bernoulli RFS: 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.
  • B. PHD and Bernoulli RFS: 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.
  • B. PHD and Bernoulli RFS: 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.
  • B. PHD and Bernoulli RFS: 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.
  • B. PHD and Bernoulli RFS: 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.

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).
  • D. Bernoulli RFS Birth Model: 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.
  • D. Bernoulli RFS Birth Model: 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.
  • D. Bernoulli RFS Birth Model: 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.
  • D. Bernoulli RFS Birth Model: 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.
  • D. Bernoulli RFS Birth Model: 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.

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.

  • Each grid cell’s posterior state is represented by a Bernoulli RFS encoding its dynamic state and occupancy probability.
  • The filter updates individual Bernoulli RFS instances and then sums them to recover the joint PHD over all grid cells.
  • The PHD/MIB filter generalizes the binary Bayes filter without assuming a static environment.
  • Under deterministic static dynamics and uniform likelihood and clutter assumptions, the PHD/MIB occupancy update reduces to the generalized binary Bayes update.
  • The occupancy state has two possible cases: occupied and free.

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.

  • Particles are random samples of the posterior PHD, represented as weighted particle sets.
  • Prediction propagates persistent-object particles through a proposal density and scales their weights by persistence probability.
  • The filter transforms the joint PHD into independent Bernoulli RFSs and applies the subsequent operations separately to each grid cell.
  • A cell’s predicted persistent-object existence probability is obtained from the sum of predicted particle weights in that cell.
  • New-born objects are sampled from a birth distribution, with the birth probability chosen individually for each grid cell according to its event likelihood.
  • New-born particle weights are assigned so that their sum equals the predicted existence probability of a new-born object in the cell.

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.
  • The measurement-grid update adapts particle weights for each cell, using identical rules for persistent and new-born particles.
  • When no measurement occurs in a cell, the filter applies a corresponding adapted-weight rule to both persistent and new-born particles.
  • For multi-object distributions, normalized particle weights sum to the posterior existence probability rather than necessarily to one.
  • The posterior occupancy probability of a cell is represented by the updated existence probability of a point object in that cell.
  • The posterior state of all point objects is represented by transforming the Bernoulli instances into a joint PHD.
  • New-born particles can substantially increase state-estimation uncertainty, so their influence may be deferred until a later recursion.
  • The filter resamples a constant number of particles from the joint posterior, with draw probabilities proportional to particle weights.

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.
  • The DS-PHD/MIB filter uses Dempster-Shafer masses to avoid representing unobserved areas with particles.
  • The DS-PHD/MIB approximation reduces the required number of particles and is easier to implement than the original particle-based filter.
  • Each cell stores separate masses for occupied and free states within the frame of discernment {O, F}.
  • The filter represents occupied mass with particle-weight sums and obtains occupancy probability through the pignistic transformation.
  • Prediction propagates particles and separately models free-space evidence with a time-dependent discount factor.
  • 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.
  • Each measurement cell supplies an occupancy BBA, a spatial likelihood, and an association probability for the update.

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.
  • Newborn particles are represented by separate particle sets for associated and unassociated spatial measurements.
  • Persistent particles are updated by multiplying their weights with the spatial measurement likelihood and then normalizing them.
  • Associated newborn particles are sampled from the state density conditioned on the measurement, whereas unassociated newborn particles are sampled from the birth distribution.
  • Newborn particle sets are created only in grid cells whose measurement mass indicates occupancy, and their particle counts follow the corresponding occupancy masses.
  • The posterior state combines the union of the particle sets with the grid cell’s posterior free mass.

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.

  • Resampling uses the original PHD/MIB resampling step.
  • The particle-based DS-PHD/MIB implementation targets massively parallel processing systems such as graphics processing units.
  • Its main implementation challenges are assigning particles to grid cells efficiently and computing cell moments independently of per-cell particle counts.
  • Particles are sorted by predicted grid cell index, enabling direct cell assignment and efficient accumulation of particle-state values.
  • The sorted representation supports standard GPU routines for random sampling, sorting, and 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: Assignment sorts particles by predicted cell and records the first and last particle indices for each cell.
  • Grid-cell occupancy update: Occupancy prediction and update accumulate particle weights, combine predicted occupancy with measurement occupancy, and store newborn masses separately.
  • Persistent-particle update: Persistent-particle updates calculate unnormalized likelihood-weighted particle weights, accumulate them, and normalize them using cell-level factors.
  • Particle prediction: Particle prediction runs in parallel and updates each particle’s state and predicted grid cell index.
  • Particle initialization: New particles are allocated per grid cell in proportion to newborn occupancy mass using a normalized lookup array.
  • Data structures: The implementation uses fixed-size arrays for particles, velocity components, squared velocities, and resampling support.

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:: The mean, variance, and covariance of two-dimensional cell velocity are computed from updated, normalized persistent particles.
  • 6) Statistical Moments of Grid Cells:: Parallel accumulation computes velocity sums with per-cell complexity independent of the number of particles assigned to a cell.
  • Evaluation: The evaluation uses real-world laser and radar data to test velocity estimation, dynamic-static separation, and computation time.
  • Evaluation: The test vehicle uses a four-layer laser scanner and two short-range radars, with ego motion compensated from vehicle speed and yaw rate.
  • Evaluation: 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.
  • Velocity estimation: For the Segway experiment, the constant-velocity process model delays estimated velocity during acceleration, while pB = 0.005 and pB = 0.02 converge closely during constant velocity.
  • Velocity estimation: Radar Doppler fusion reduces remaining bias and accelerates convergence during strong deceleration.

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.
  • Consistency under birth-probability variation: 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.
  • 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.
  • Sensor fusion: Radar fusion reduces false positive movement estimates compared with laser-only sensing.Doppler measurements help reduce false positive movement estimation in grid cells.
  • 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.
Loading 1605.02406v2…