A Unified View of Algorithms for Path Planning Using Probabilistic Inference on Factor Graphs

• URL: http://arxiv.org/abs/2106.10442v1
• Date: Sat, 19 Jun 2021 07:13:15 GMT
• Title: A Unified View of Algorithms for Path Planning Using Probabilistic Inference on Factor Graphs
• Authors: Francesco A.N. Palmieri and Krishna R. Pattipati and Giovanni Di Gennaro and Giovanni Fioretti and Francesco Verolla and Amedeo Buonanno
• Abstract summary: This work looks at the specific recursions that arise from various cost functions that, although they may appear similar in scope, bear differences, at least when applied to typical path planning problems. We show how this unified approach, presented both in probability space and in log space, provides a very general framework that includes the Sum-product, the Max-product, Dynamic programming and mixed Reward/Entropy criteria-based algorithms.
• Score: 2.4874504720536317
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Even if path planning can be solved using standard techniques from dynamic programming and control, the problem can also be approached using probabilistic inference. The algorithms that emerge using the latter framework bear some appealing characteristics that qualify the probabilistic approach as a powerful alternative to the more traditional control formulations. The idea of using estimation on stochastic models to solve control problems is not new and the inference approach considered here falls under the rubric of Active Inference (AI) and Control as Inference (CAI). In this work, we look at the specific recursions that arise from various cost functions that, although they may appear similar in scope, bear noticeable differences, at least when applied to typical path planning problems. We start by posing the path planning problem on a probabilistic factor graph, and show how the various algorithms translate into specific message composition rules. We then show how this unified approach, presented both in probability space and in log space, provides a very general framework that includes the Sum-product, the Max-product, Dynamic programming and mixed Reward/Entropy criteria-based algorithms. The framework also expands algorithmic design options for smoother or sharper policy distributions, including generalized Sum/Max-product algorithm, a Smooth Dynamic programming algorithm and modified versions of the Reward/Entropy recursions. We provide a comprehensive table of recursions and a comparison through simulations, first on a synthetic small grid with a single goal with obstacles, and then on a grid extrapolated from a real-world scene with multiple goals and a semantic map.

Related papers

• Deterministic Trajectory Optimization through Probabilistic Optimal Control [3.2771631221674333]
  We propose two new algorithms for discrete-time deterministic finite-horizon nonlinear optimal control problems. Both algorithms are inspired by a novel theoretical paradigm known as probabilistic optimal control. We show that the application of this algorithm results in a fixed point of probabilistic policies that converge to the deterministic optimal policy.
  arXiv  Detail & Related papers  (2024-07-18T09:17:47Z)
• Doubly Stochastic Matrix Models for Estimation of Distribution Algorithms [2.28438857884398]
  We explore the use of Doubly Matrices (DSM) for matching and assignment nature permutation problems. Specifically, we adopt the framework of estimation of distribution algorithms and compare DSMs to some existing proposals for permutation problems. Preliminary experiments on instances of the quadratic assignment problem validate this line of research and show that DSMs may obtain very competitive results.
  arXiv  Detail & Related papers  (2023-04-05T14:36:48Z)
• Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
  We present a new algorithm for a policy gradient in TMDPs by a simple extension of the proximal policy optimization (PPO) algorithm. We demonstrate this on a real-world multiple-objective navigation problem with an arbitrary ordering of objectives both in simulation and on a real robot.
  arXiv  Detail & Related papers  (2022-09-15T07:22:58Z)
• Accelerating ERM for data-driven algorithm design using output-sensitive techniques [26.32088674030797]
  We study techniques to develop efficient learning algorithms for data-driven algorithm design. Our approach involves two novel ingredients -- an output-sensitive algorithm for enumerating polytopes induced by a set of hyperplanes. We illustrate our techniques by giving algorithms for pricing problems, linkage-based clustering and dynamic-programming based sequence alignment.
  arXiv  Detail & Related papers  (2022-04-07T17:27:18Z)
• The Parametric Cost Function Approximation: A new approach for multistage stochastic programming [4.847980206213335]
  We show that a parameterized version of a deterministic optimization model can be an effective way of handling uncertainty without the complexity of either programming or dynamic programming. This approach can handle complex, high-dimensional state variables, and avoids the usual approximations associated with scenario trees or value function approximations.
  arXiv  Detail & Related papers  (2022-01-01T23:25:09Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  We prove that the generalization error of an optimization algorithm can be bounded on the complexity' of the fractal structure that underlies its generalization measure. We further specialize our results to specific problems (e.g., linear/logistic regression, one hidden/layered neural networks) and algorithms.
  arXiv  Detail & Related papers  (2021-06-09T08:05:36Z)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  Joint network topology inference represents a canonical problem of learning multiple graph Laplacian matrices from heterogeneous graph signals. We propose a general graph estimator based on a novel structured fusion regularization. We show that the proposed graph estimator enjoys both high computational efficiency and rigorous theoretical guarantee.
  arXiv  Detail & Related papers  (2021-03-05T04:42:32Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  Maximum a posteriori (MAP) inference in discrete-valued random fields is a fundamental problem in machine learning. Due to the difficulty of this problem, linear programming (LP) relaxations are commonly used to derive specialized message passing algorithms. We present randomized methods for accelerating these algorithms by leveraging techniques that underlie classical accelerated gradient.
  arXiv  Detail & Related papers  (2020-07-01T18:43:32Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  We present a general framework for mining constraints from data. In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem. We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
  arXiv  Detail & Related papers  (2020-06-18T20:09:53Z)
• Generating Random Logic Programs Using Constraint Programming [12.47276164048813]
  We present a novel approach to generating random logic programs using constraint programming. We show how the model scales with parameter values, and use the model to compare probabilistic inference algorithms across a range of synthetic problems.
  arXiv  Detail & Related papers  (2020-06-02T19:12:53Z)
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies [83.05591911173332]
  junction tree algorithm is the most general solution for exact MAP inference with run-time guarantees. We propose a new graph transformation technique via node cloning which ensures a run-time for solving our target problem independently of the form of a corresponding clique tree.
  arXiv  Detail & Related papers  (2019-12-27T13:30:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.