PaperlayerView exact revision on arXiv

Source-linked AI summary

A Catalog of Probability Generating Functionals for Multitarget Tracking and Data Assignment Problems

Roy L. Streit

arXiv:2608.29297v1eess.SY

TL;DR

Bayesian tracking filters often require exact probabilistic representations of target-measurement and assignment processes, but their posterior recursions and particle-weight calculations can be computationally difficult. This paper catalogs their PGFLs across labeled, unlabeled, and hybrid targets, derives new trajectory and assignment PGFs, and applies saddle-point methods to particle weights. For J-PDA, the approximation has complexity at most O(N^2.4), while exact particle-weight computation is NP-hard.

  • Problem

    The paper addresses how to derive unified, exact PGFL representations for diverse Bayesian tracking filters and use them when posterior recursions or assignment calculations are computationally difficult.

  • Method

    The paper catalogs PGFLs for labeled, unlabeled, and hybrid tracking problems, derives trajectory and assignment PGFs, and approximates mixed derivatives with the saddle point method.

  • Results

    For J-PDA particle weights, the saddle-point approximation has complexity at most O(N^2.4), whereas exact particle-weight computation is NP-hard.

  • Takeaways & Limitations

    PGFLs organize many tracking filters within one probabilistic and combinatorial framework and provide exact expressions for assignment probabilities and posterior calculations.

  • Takeaways & Limitations

    Unlabeled-target filters on discrete state spaces that require high-order mixed ordinary derivatives are outside the paper's scope.

Abstract

from arXiv · show

This paper studies the class of Bayesian tracking filters for which the probability generating functional of the joint target-measurement process can be derived from the statistical assumptions that define the problem. The class includes filters for labeled and unlabeled targets, as well as hybrid filters in which both labeled and unlabeled targets are present. New results include the probability generating functional for interval filtering of target trajectories for both labeled an unlabeled targets, and a novel method for computing the probability generating function of measurement-to-target assignment probabilities. Probability generating functionals give exact expressions for calculating the importance weights in particle filter implementations. Low computational complexity approximations to the particle weights are derived from the probability generating functionals via the saddle point method.

I. INTRODUCTION

The paper organizes a broad class of Bayesian tracking filters through probability generating functionals (PGFLs), deriving exact probabilistic and combinatorial representations across labeled, unlabeled, and hybrid targets. It also introduces assignment PGFs, trajectory-process PGFLs, and saddle-point approximations for particle weights.

  • I. INTRODUCTION: PGFLs provide a unified catalog of Bayesian tracking filters whose probabilistic and combinatorial structures can be expressed exactly.The catalog covers PDA filters for labeled targets, intensity filters for unlabeled targets, and hybrid filters.
  • I. INTRODUCTION: The paper argues by example that PGFLs are elegant, concise, and complete models of the assumptions underlying many tracking filters.The authors present this perspective as a tool for posing and solving tracking problems.
  • Contributions:: PGFs for measurement assignments include multisensor assignments and J-PDA assignments, with permanent ratios recovered as derivatives of a general PGF.The derivative formulation shows that the permanent expression is not an isolated result.
  • Contributions:: Trajectory filtering is modeled with a state-dependent time-inhomogeneous branching process, whose marginal trajectory-count prior is the classical state-dependent Galton-Watson process.The process is initiated by a single target and supports labeled and unlabeled trajectory filters.
  • Contributions:: The paper derives PGFLs for additional tracking problems, including joint localization with unknown numbers of targets and sensors and hybrid tracking of a labeled target in a swarm.These problems are identified as subjects for future work and are not explored further in the paper.
  • Contributions:: Saddle-point approximation reduces J-PDA particle-weight computation from an NP-hard exact problem to complexity at most O(N^2.4).The approximation avoids symbolic differentiation of mixed PGFL derivatives when evaluating particle weights.

IV. SINGLE TARGET TRACKING

The single-target section develops PGFL formulations for Bayes-Markov, missed-detection, PDA, and related filters. It represents target measurements and false alarms as point processes, then obtains posterior processes and assignment probabilities through normalized PGFL derivatives.

  • Single-target filter classes: Bayes-Markov filtering assumes no false alarms, while BMD adds missed-detection uncertainty and PDA superposes target measurements with an independent false-alarm process.The PDA measurements are unlabeled with respect to their target or false-alarm origin.
  • Bayes-Markov and BMD: The basic single-target PGFL permits exactly one target and one measurement, whereas BMD permits exactly one target and at most one measurement.The BMD model uses detection probability Pd(x) and nondetection probability Qd(x) = 1 − Pd(x).
  • Probabilistic data association: PDA models false alarms as distinct i.i.d. points with pdf pFA(y), with a random non-negative count described by a PGF.The false-alarm process is independent of the target measurement process.
  • Posterior calculation: The posterior PGFL is obtained from the joint PGFL by a normalized mixed first-order derivative with respect to the observed measurements.For an empty measurement set, no derivatives are taken.
  • Posterior calculation: Measurement-to-target assignment probabilities are computed directly from the PGFL using the method developed for assignment problems.The same PGFL framework also yields the posterior target pdf through normalized derivatives.

D. Integrated PDA (IPDA)

IPDA extends PDA with uncertainty about target presence, while IMM-PDA extends PDA with uncertainty about maneuvering modes. Their PGFLs encode these uncertainties and support posterior existence, mode, and state inference.

  • Integrated PDA: IPDA models target presence or absence with a two-state Markov chain and predicted existence probability χ−.The filter is also called a Bernoulli filter.
  • Integrated PDA: IPDA nonzero events contain at most one target and any number of measurements, reflecting target-existence uncertainty combined with false alarms.Different false-alarm processes produce different IPDA filters.
  • Integrated PDA: The IPDA formulation generalizes to state-dependent existence probability functions χ = χ(x).This extension follows from an equivalent form of the IPDA PGFL.
  • IMM-PDA: IMM-PDA represents maneuvering targets on the joint state space X × S, where a Markov chain models shifts among motion modes.The target state and mode are represented by separate indeterminates in the PGFL.
  • IMM-PDA: In the no-missed-detection, no-clutter case, the coefficient of js gives the Bayesian posterior probability of mode s given the measurement.Setting all mode indeterminates to one instead gives the PGFL of the target state process.
  • IMM-PDA: The IMM filter output is a pdf on X × S represented by mode-specific filters together with Bayesian updated mode probabilities.This separates continuous target-state inference from discrete mode inference.

V. LABELED MULTITARGET TRACKING

The labeled multitarget filters are formulated by combining single-target PGFLs under independence assumptions, with extensions for missed detections, false alarms, and multiple target models. Exact posterior forms expose both combinatorial assignment structure and computational limits.

  • Multitarget construction: The multitarget PGFL is the product of independent single-target PGFLs, preserving single-target structure while increasing combinatorial complexity.The formulation accommodates a specified number N ≥ 1 of targets and multiple target models.
  • Joint BM: Joint BM assigns exactly N measurements one-to-one to N targets, so nonzero events contain exactly N targets and N measurements.Each target generates exactly one measurement.
  • Joint BMD: Joint BMD allows each target to independently miss detection, yielding exactly N targets and at most N measurements.The detection probability is state dependent through Pdn(xn).
  • Joint PDA: Joint PDA superposes an independent false-alarm process on target measurements, producing exactly N targets and potentially any number of measurements under Poisson false alarms.Its posterior approximation reimposes target independence through a mean-field product of marginal processes.
  • Computational limitation: J-PDA assignment probabilities are NP-hard because even restricted cases require computing a matrix permanent or its generalization.This makes the filter impractical for large N.
  • Joint IPDA: J-IPDA posterior PGFLs are mixtures of labeled multiBernoulli processes, but repeated recursion rapidly increases mixture terms and prevents strict closure.Reducing the exact posterior to the prior order is necessary for an implementable filter.

E. Joint Interacting Multiple Model

The joint IMM-J-PDA formulation extends labeled PDA tracking so different targets can switch among target-specific motion modes. Its PGFL uses mode-index variables and is closed with a mean-field approximation.

  • Mode model: Each target has a target-specific mode set and Markov transition matrix, allowing targets to maneuver in different ways.Mode switching is modeled independently through a Markov chain on Sn.
  • Heterogeneous targets: Target-specific motion and measurement models may differ across targets and modes.The mode-specific predicted target densities retain the single-target IMM-PDA form.
  • PGFL formulation: The IMM-J-PDA PGFL labels each target state with an indeterminate function and each mode with a complex-valued variable.The joint mode index collects the mode variables for all targets.
  • Recursion: The IMM extension obtains a marginal PGFL by setting other targets' functions and mode variables to one, then uses a mean-field approximation to close the Bayes recursion.The resulting marginal depends only on the selected target's function and mode indices.
  • Multisensor assumptions: The multisensor extension assumes known sensor origins and states, conditionally independent sensor measurements, and registered sensor frames.Measurements are processed jointly at a fusion center.

A. Multisensor J-BMD

The multisensor J-BMD framework superposes independent labeled target processes across conditionally independent sensors, then adds sensor-specific false alarms for multisensor PDA and IPDA variants. It also establishes the unlabeled transition by replacing target-specific functions with a common function.

  • Multisensor J-BMD: MS-J-BMD superposes N independent labeled multisensor BMD processes across L sensors without false alarms.Each sensor can detect a target at most once under the BMD model.
  • Multisensor J-BMD: MS-J-BMD events contain exactly N targets and at most N measurements in each sensor.This follows from conditional independence and the per-target BMD assumptions.
  • Multisensor PDA: MS-J-PDA adds independent, potentially sensor-specific false-alarm processes to MS-J-BMD.With Poisson false alarms, each sensor can produce any number of measurements.
  • Multisensor IPDA: MS-J-IPDA has the same multisensor structure as MS-J-PDA, replacing the target measurement model with the appropriate multisensor IBMD model.With Poisson false alarms, events have at most N targets and any number of measurements in each sensor.
  • Unlabeled transition: Unlabeled tracking replaces all target-specific functions hn with a common h, superposing target processes and often reducing derivative complexity.The resulting points are indistinguishable, so target-measurement identities are unavailable.
  • Unlabeled J-BM: For U-J-BM with identical target models, nonzero events contain exactly N unidentifiable targets and N measurements.The assignment count is fixed, but which target generated which measurement is unknown.
  • Random target counts: Random target counts yield unlabeled processes with random target numbers and, for BMD, no more measurements than targets.The predicted target-count PGF is an input to the random-number formulation.

C. Unlabeled J-PDA and J-IPDA Targets

Unlabeled PDA, IPDA, CPHD, and PHD filters arise by superposing unlabeled target processes with false alarms and, when needed, randomizing target counts. The unlabeled formulation can be substantially cheaper, while pooled unknown-sensor problems introduce additional modeling assumptions and open practicality questions.

  • Unlabeled PDA/IPDA: The U-J-PDA intensity filter has complexity O(NM), substantially below the NP-hard complexity of labeled J-PDA.U-J-PDA and U-J-IPDA model target measurements without target labels and allow false alarms.
  • Unlabeled PDA/IPDA: U-J-BMD and U-J-IPDA are binomial intensity filters because the Nth power of a Bernoulli PGF is a binomial PGF.With Poisson false alarms, U-J-PDA has exactly N targets and any number of measurements, while U-J-IPDA has up to N targets.
  • CPHD and PHD: The CPHD filter is obtained by mixing the U-J-PDA PGFL over a random target count using the predicted target-count PGF.Its inputs are the predicted target-count PGF and predicted target-process distribution.
  • CPHD and PHD: The U-J-PDA, IPDA, and U-J-IPDA filters are special cases of CPHD, while Poisson target and false-alarm counts yield the PHD filter.The PHD model permits any number of targets and measurements.
  • PHD limitation: The PHD recursion is not closed because its exact posterior is not a Poisson point process, so the filter approximates it with a Poisson process matching the posterior intensity.The prior process is assumed to be a PPP.
  • Multisensor unlabeled tracking: Multisensor unlabeled filters superpose target processes and independent sensor false alarms, extending the labeled multisensor construction to heterogeneous sensors.The multisensor CPHD and PHD variants follow by randomizing target counts and specializing to Poisson counts.
  • Unknown sensors: The pooled forensic formulation removes sensor labels and sensor count, models sensors as a finite point process, and assumes homogeneous conditionally independent sensors.Its practicality is explicitly identified as an open question.

IX. HYBRID LABELED AND UNLABELED TARGETS

This section develops PGFL formulations for hybrid tracking problems involving labeled and unlabeled targets, including target swarms and fluctuating target highlights. It also shows how point-target formulations extend to extended targets.

  • Hybrid labeled and unlabeled tracking: The swarm problem tracks one labeled target of interest without individually tracking a heterogeneous mixture of known and unknown targets.The swarm can be large enough that tracking every target solely to maintain the target-of-interest track is impractical.
  • Hybrid labeled and unlabeled tracking: Hybrid filters combine labeled targets with unlabeled target processes, including unknown or not-yet-detected targets.The unlabeled process may be modeled as a Poisson point process or with a more general model.
  • Hybrid labeled and unlabeled tracking: The paper derives PGFLs for additional hybrid problems, including pooled unlabeled sensor measurements and target-of-interest tracking in a heterogeneous swarm.These formulations are presented as examples for future work rather than explored further in the paper.
  • J-PDA with target highlights: For JiFi, the exact posterior is not Poisson, but its joint intensity factors into one intensity function for each target highlight process.The recursion is closed by approximating the posterior as a product of PPPs with those posterior intensities.
  • General extended targets: Extended-target PGFLs are obtained by replacing point-target BMD PGFLs with PGFLs for random numbers of measurements, for both labeled and unlabeled problems.The paper identifies JiFi as a prominent example of this replacement method.

A. PGFL for Trajectories Initialized by One Target

The paper models a single target’s trajectory and measurements as a state-dependent, time-inhomogeneous branching process over a finite observation interval. Its joint PGFL is computed by backward recursion.

  • Model: A target transitions between time-indexed state spaces according to transition densities and generates a random number of measurements at each scan.The model includes the conditional measurement PGF for a target at each state.
  • Model: Branching allows a target at time k−1 to produce a random number of targets at time k, including termination, birth-death, and cascading growth cases.The zero-offspring probability represents termination, while higher-order PGF terms allow the target count to grow through cascades.
  • Backward recursion: The joint target-measurement PGFL over the observation interval is computed by a backward recursion from scan K to scan 1.The recursion combines measurement processes, branching probabilities, and state transitions before applying the initialization prior.
  • Backward recursion: The recursion is summarized algorithmically by iterating backward over scans and then computing the PGFL for all single-target trajectories.The result is the building block for interval filtering of labeled and unlabeled target trajectories.
  • Trajectory realizations: Trajectory realizations can contain multiple measurement segments because imperfect detection may interrupt otherwise continuous trajectory observations.A realization may begin and end within the interval, and may contain several singleton-measurement segments.
  • Additional processes: Independent false-alarm processes are included at each time, and immigrant targets use the same recursion with an appropriate starting time and motion model.The PGFL of superposed trajectory processes is formed from the component PGFLs under independence.

B. PGFL for a Known Number of Targets

The section constructs PGFLs for interval target-trajectory filters with known target populations, then obtains priors, posteriors, intensities, and assignment probabilities through derivatives and labeled or unlabeled representations.

  • Known target trajectories: Known labeled target trajectories have individual PGFLs whose product gives the joint trajectory PGFL under independent target and false-alarm processes.Removing labels by using a common indeterminate function yields an interval unlabeled J-PDA PGFL.
  • Posterior quantities: The interval PGFL supports marginalization over trajectory histories and posterior intensities through normalized mixed first-order derivatives.The posterior intensity at time K counts expected trajectories ending at each state.
  • Posterior quantities: A sliding batch interval filter makes one approximation instead of K one-step approximations, reducing accumulated-artifact risk at increased computational complexity.The paper identifies sliding batch intensity filters as remaining to be studied.
  • Count distributions: Setting trajectory indeterminates to scalar variables produces PGFs for trajectory counts, whose coefficients give prior and conditional count probabilities.The final-time count PGF follows by setting earlier variables to one; conditional coefficients are obtained after measurement conditioning.
  • Assignment probabilities: The secular method converts measurement-assignment PGFL calculations into ordinary-function derivatives, whose normalized monomial coefficients represent feasible assignment probabilities.For the single-target PDA example, the feasible assignments include missed detection and each measurement assigned to the target.

B. Example 2: Multitarget J-PDA

The multitarget J-PDA example encodes measurement-to-target assignments in a polynomial derivative of the PGFL, but evaluating that derivative is NP-hard because it contains matrix-permanent calculations.

  • Assignment representation: The J-PDA secular function labels each measurement by its possible target assignment, while false-alarm assignments need not be labeled.The resulting derivative is a multivariate polynomial in the assignment labels.
  • Assignment probabilities: The coefficients of the derivative’s monomials are conditional probabilities for feasible assignments of measurements to the N targets.The derivative is evaluated at an all-zero measurement-variable array after normalization by the all-one value.
  • Computational complexity: In the no-false-alarm, no-missed-detection case, the assignment derivative reduces to a matrix permanent.The permanent sums products over all permutations of target-measurement pairings.
  • Scope: More general assignment cases can use rectangular-matrix permanent generalizations, but those results are not presented.The section therefore leaves the generalized formulas outside its developed examples.

C. Example 3: Multiple Sensor J-BMD

The multiple-sensor J-BMD example forms assignment probabilities by combining sensor-level PGFL derivatives, with each monomial identifying a feasible multisensor assignment and its coefficient giving that assignment’s probability.

  • Model assumptions: The model assumes multisensor labeled targets and no false tracks from sensor-level tracking systems, with false-track PGFLs added if needed.The relevant base model is the multisensor labeled J-BMD problem.
  • Assignment representation: Each assignment variable identifies a measurement from sensor ℓ assigned to target n, and the full set contains NML indeterminates.Sensor measurements are indexed by sensor, measurement, and target.
  • Sensor-level assignments: For two measurements at one sensor, the derivative term gives the probability that those measurements are assigned to two specified targets and no other targets are detected.The associated double sum covers all feasible assignments of two targets to the two measurements.
  • Joint assignments: Multiplying sensor-level derivatives yields N^ML monomials, each encoding a feasible multisensor assignment with its coefficient as the assignment probability.The resulting product implies conditional independence of the de novo assignment variables across sensors.
  • Interpretation: The resulting expression is not itself a joint PGF of random assignments because assignments are not random variables unless such variables are defined separately.A normalized function is introduced to define a probability law for de novo assignment variables.

XII. SADDLE POINT APPROXIMATION

The saddle point method approximates exact PGFL-derived particle weights by converting derivatives into multivariate Cauchy integrals and numerically evaluating those integrals near saddle points, reducing computational cost for J-PDA.

  • Motivation: Exact particle weights are high-complexity derivatives of PGFLs, motivating saddle point approximations for particle-filter implementations.The method is illustrated using the labeled J-PDA filter, whose exact filter is NP-hard.
  • Method: The approximation pipeline takes three steps: identify particle weights with PGFL derivatives, rewrite derivatives as multivariate Cauchy integrals, and approximate integrals at saddle points.Only real-valued numerical methods are required for the final computation.
  • Method: The saddle point is found by minimizing a real-valued function over contour radii, then the particle weight is approximated using the saddle point and Hessian.The saddle point depends on the particle state through the PGFL.
  • Complexity: O(N^2.373) is the stated upper complexity for computing an N × N determinant when the number of measurements exceeds the number of targets.The reduction from an m × m determinant uses the Weinstein-Aronszajn identity.
  • Numerical properties: For J-PDA, the minimization problem has a unique solution because its non-polynomial PGFL has non-negative power-series coefficients.The paper attributes this property to the presence of false alarms.
  • Limitations: Approximation quality requires case-by-case examination because general error analysis is difficult, although higher-order terms can be derived if needed.Alternative mean-field approximations can avoid the full Hessian and determinant.
  • Scope: Superposing labeled PGFLs can change computational complexity substantially: the paper contrasts NP-hard labeled J-PDA with lower-complexity unlabeled U-J-PDA.This illustrates how representation choices affect the resulting filter complexity.

APPENDIX PGFS AND PGFLS FOR FINITE POINT PROCESSES

The appendix develops PGFs and PGFLs for finite point processes, including i.i.d. and i.i.d. cluster processes, and shows how derivatives recover probabilities and densities.

  • PGFs: Bernoulli and Poisson distributions provide common tracking examples, with PGFs encoding their cardinality distributions.Multivariate PGFs extend the same construction, while Bayes' theorem appears as a normalized mixed higher-order derivative.
  • Finite point processes: i.i.d. finite point processes model multisets with random cardinality and unlabeled, identically distributed samples.On continuous spaces without point masses, realizations are sets with probability one because samples are distinct.
  • Finite point processes: Independent superposition multiplies constituent PGFLs, allowing complex tracking models to be derived from their component processes.The resulting points are unlabeled, so their generating functional captures the combined process without source identities.
  • Derivative recovery: Mixed derivatives of secular functions recover realization probabilities or densities from PGFLs.For distinct points x1:n, evaluating the mixed first-order derivative at zero yields the density of the corresponding realization.
  • PGFL construction: Continuous-space PGFLs arise by gridding the space, constructing a discrete PGF, and taking a small-cell limit under integrability conditions.The derivation initially raises a well-definedness issue for limits of indeterminate step functions; restricting h to locally integrable functions resolves it.
  • Derivative recovery: Intensity functions can be computed by substituting a delta-based test function into the PGFL and differentiating the resulting secular function.This procedure connects PGFL representations to point-process intensity calculations.

B. Bivariate Cluster Processes and Bayes Theorem

The paper models targets and measurements as a bivariate i.i.d. cluster process, then uses normalized mixed derivatives to obtain the Bayes posterior PGFL after conditioning on measurements.

  • Bivariate cluster processes: A bivariate finite point process combines a target process on X with a measurement process on Y; the i.i.d. cluster subclass is used for tracking.Each target generates a conditionally independent measurement point process governed by p(y|x).
  • Bivariate cluster processes: The measurement process is formed by superposing one i.i.d. measurement process for each target realization.The resulting joint target-measurement model has a PGFL obtained from the i.i.d. cluster-process construction.
  • Bayes theorem: The joint probability distribution is encoded in first-order derivatives of the bivariate secular function.Differentiating with respect to all target and measurement variables yields the joint density for a specified realization.
  • Bayes theorem: The Bayes posterior PGFL is the normalized mixed first-order derivative with respect to measurement variables after conditioning on observed measurements.When exactly one target is possible, the posterior process reduces to a random variable and its intensity is the Bayes posterior pdf.
  • Bayes theorem: The general derivation is applied explicitly to the probability generating functional of the PDA filter.The paper points to the PDA derivation as a detailed example of the procedure.
Loading 2608.29297v1…