A dynamic programming algorithm for informative measurements and near-optimal path-planning

• URL: http://arxiv.org/abs/2109.11808v1
• Date: Fri, 24 Sep 2021 08:40:06 GMT
• Title: A dynamic programming algorithm for informative measurements and near-optimal path-planning
• Authors: Peter N. Loxley and Ka Wai Cheung
• Abstract summary: An informative measurement is the most efficient way to gain information about an unknown state. We give a first-principles derivation of a general-purpose dynamic programming algorithm that returns a sequence of informative measurements. This algorithm can be used by an autonomous agent or robot to decide where best to measure next.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: An informative measurement is the most efficient way to gain information about an unknown state. We give a first-principles derivation of a general-purpose dynamic programming algorithm that returns a sequence of informative measurements by sequentially maximizing the entropy of possible measurement outcomes. This algorithm can be used by an autonomous agent or robot to decide where best to measure next, planning a path corresponding to an optimal sequence of informative measurements. This algorithm is applicable to states and controls that are continuous or discrete, and agent dynamics that is either stochastic or deterministic; including Markov decision processes. Recent results from approximate dynamic programming and reinforcement learning, including on-line approximations such as rollout and Monte Carlo tree search, allow an agent or robot to solve the measurement task in real-time. The resulting near-optimal solutions include non-myopic paths and measurement sequences that can generally outperform, sometimes substantially, commonly-used greedy heuristics such as maximizing the entropy of each measurement outcome. This is demonstrated for a global search problem, where on-line planning with an extended local search is found to reduce the number of measurements in the search by half.

Related papers

• Reinforced Disentanglers on Random Unitary Circuits [0.10923877073891444]
  We search for efficient disentanglers on random Clifford circuits of two-qubit gates arranged in a brick-wall pattern. Disentanglers are defined as a set of projective measurements inserted between consecutive entangling layers.
  arXiv  Detail & Related papers  (2024-11-14T19:51:26Z)
• MEXGEN: An Effective and Efficient Information Gain Approximation for Information Gathering Path Planning [3.195234044113248]
  Planning algorithms for autonomous robots need to solve sequential decision making problems under uncertainty. We develop a computationally efficient and effective approximation for the difficult problem of predicting the likely sensor measurements from uncertain belief states. We demonstrate improved performance gains in radio-source tracking and localization problems using extensive simulated and field experiments with a multirotor aerial robot.
  arXiv  Detail & Related papers  (2024-05-04T08:09:16Z)
• Machine-learning optimized measurements of chaotic dynamical systems via the information bottleneck [4.189643331553922]
  A perfect measurement captures all of the information created by the system's evolution with minimal redundancy. Finding an optimal measurement is challenging, and has generally required intimate knowledge of the dynamics in the few cases where it has been done. We employ machine learning to optimize measurement processes that efficiently extract information from trajectory data.
  arXiv  Detail & Related papers  (2023-11-08T18:56:29Z)
• On efficient computation in active inference [1.1470070927586016]
  We present a novel planning algorithm for finite temporal horizons with drastically lower computational complexity. We also simplify the process of setting an appropriate target distribution for new and existing active inference planning schemes.
  arXiv  Detail & Related papers  (2023-07-02T07:38:56Z)
• Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL [106.82295532402335]
  Existing reinforcement learning algorithms suffer from computational intractability, strong statistical assumptions, and suboptimal sample complexity. We provide the first computationally efficient algorithm that attains rate-optimal sample complexity with respect to the desired accuracy level. Our algorithm, MusIK, combines systematic exploration with representation learning based on multi-step inverse kinematics.
  arXiv  Detail & Related papers  (2023-04-12T14:51:47Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  We study a learning-augmented variant of the classical, notoriously hard online graph exploration problem. We propose an algorithm that naturally integrates predictions into the well-known Nearest Neighbor (NN) algorithm.
  arXiv  Detail & Related papers  (2021-12-10T10:02:31Z)
• C-Planning: An Automatic Curriculum for Learning Goal-Reaching Tasks [133.40619754674066]
  Goal-conditioned reinforcement learning can solve tasks in a wide range of domains, including navigation and manipulation. We propose the distant goal-reaching task by using search at training time to automatically generate intermediate states. E-step corresponds to planning an optimal sequence of waypoints using graph search, while the M-step aims to learn a goal-conditioned policy to reach those waypoints.
  arXiv  Detail & Related papers  (2021-10-22T22:05:31Z)
• Anomaly Detection via Controlled Sensing and Deep Active Inference [43.07302992747749]
  In this paper, we address the anomaly detection problem where the objective is to find the anomalous processes among a given set of processes. We develop a sequential selection algorithm that decides which processes to be probed at every instant to detect the anomalies. Our algorithm is based on active inference which is a general framework to make sequential decisions in order to maximize the notion of free energy.
  arXiv  Detail & Related papers  (2021-05-12T17:54:02Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  We present a meta-algorithm that adapts to the optimal complexity with $tildeO(L5/6 T2/3)$ regret. We also show that the meta-algorithm automatically admits significantly improved instance-dependent regret bounds.
  arXiv  Detail & Related papers  (2020-11-19T10:00:54Z)
• Active Model Estimation in Markov Decision Processes [108.46146218973189]
  We study the problem of efficient exploration in order to learn an accurate model of an environment, modeled as a Markov decision process (MDP) We show that our Markov-based algorithm outperforms both our original algorithm and the maximum entropy algorithm in the small sample regime.
  arXiv  Detail & Related papers  (2020-03-06T16:17:24Z)

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.