Cost Aware Asynchronous Multi-Agent Active Search

• URL: http://arxiv.org/abs/2210.02259v1
• Date: Wed, 5 Oct 2022 13:38:30 GMT
• Title: Cost Aware Asynchronous Multi-Agent Active Search
• Authors: Arundhati Banerjee, Ramina Ghods and Jeff Schneider
• Abstract summary: We introduce an online active search algorithm to detect targets in an unknown environment. Our algorithm combines principles from Thompson Sampling, Monte Carlo Tree Search and pareto-optimal confidence bounds. We analyze the algorithm's performance in simulation to show its efficacy in cost aware active search.
• Score: 6.587280549237275
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-agent active search requires autonomous agents to choose sensing actions that efficiently locate targets. In a realistic setting, agents also must consider the costs that their decisions incur. Previously proposed active search algorithms simplify the problem by ignoring uncertainty in the agent's environment, using myopic decision making, and/or overlooking costs. In this paper, we introduce an online active search algorithm to detect targets in an unknown environment by making adaptive cost-aware decisions regarding the agent's actions. Our algorithm combines principles from Thompson Sampling (for search space exploration and decentralized multi-agent decision making), Monte Carlo Tree Search (for long horizon planning) and pareto-optimal confidence bounds (for multi-objective optimization in an unknown environment) to propose an online lookahead planner that removes all the simplifications. We analyze the algorithm's performance in simulation to show its efficacy in cost aware active search.

Related papers

• Tree Search for Language Model Agents [69.43007235771383]
  We propose an inference-time search algorithm for LM agents to perform exploration and multi-step planning in interactive web environments. Our approach is a form of best-first tree search that operates within the actual environment space. It is the first tree search algorithm for LM agents that shows effectiveness on realistic web tasks.
  arXiv  Detail & Related papers  (2024-07-01T17:07:55Z)
• A Dynamic LLM-Powered Agent Network for Task-Oriented Agent Collaboration [55.35849138235116]
  We propose automatically selecting a team of agents from candidates to collaborate in a dynamic communication structure toward different tasks and domains. Specifically, we build a framework named Dynamic LLM-Powered Agent Network ($textDyLAN$) for LLM-powered agent collaboration. We demonstrate that DyLAN outperforms strong baselines in code generation, decision-making, general reasoning, and arithmetic reasoning tasks with moderate computational cost.
  arXiv  Detail & Related papers  (2023-10-03T16:05:48Z)
• Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
  Modern robotics often involves multiple embodied agents operating within a shared environment. Standard sampling-based algorithms can be used to search for solutions in the robots' joint space. We integrate the concept of factorization into sampling-based algorithms, which requires only minimal modifications to existing methods. We present a general implementation of a factorized SBA, derive an analytical gain in terms of sample complexity for PRM*, and showcase empirical results for RRG.
  arXiv  Detail & Related papers  (2023-04-01T15:50:18Z)
• Multi-Agent Active Search using Detection and Location Uncertainty [6.587280549237275]
  Active search algorithms must contend with two types of uncertainty: detection uncertainty and location uncertainty. We first propose an inference method to jointly handle both target detection and location uncertainty. We then build a decision making algorithm that uses Thompson sampling to enable decentralized multi-agent active search.
  arXiv  Detail & Related papers  (2022-03-09T04:53:37Z)
• On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Game [140.19656665344917]
  We study the reward-free RL problem, where an agent aims to thoroughly explore the environment without any pre-specified reward function. We tackle this problem under the context of function approximation, leveraging powerful function approximators. We establish the first provably efficient reward-free RL algorithm with kernel and neural function approximators.
  arXiv  Detail & Related papers  (2021-10-19T07:26:33Z)
• Nonmyopic Multifidelity Active Search [15.689830609697685]
  We propose a model of multifidelity active search, as well as a novel, computationally efficient policy for this setting. We evaluate the performance of our solution on real-world datasets and demonstrate significantly better performance than natural benchmarks.
  arXiv  Detail & Related papers  (2021-06-11T12:55:51Z)
• Inverse Bayesian Optimization: Learning Human Search Strategies in a Sequential Optimization Task [0.10499611180329801]
  In this paper, we explore the inverse problem of Bayesian optimization. We estimate the agent's latent acquisition function based on observed search paths. We illustrate our methods by analyzing human behavior from an experiment.
  arXiv  Detail & Related papers  (2021-04-16T15:40:34Z)
• Selection-Expansion: A Unifying Framework for Motion-Planning and Diversity Search Algorithms [69.87173070473717]
  We investigate the properties of two diversity search algorithms, the Novelty Search and the Goal Exploration Process algorithms. The relation to MP algorithms reveals that the smoothness, or lack of smoothness of the mapping between the policy parameter space and the outcome space plays a key role in the search efficiency.
  arXiv  Detail & Related papers  (2021-04-10T13:52:27Z)
• Exploration and Incentives in Reinforcement Learning [107.42240386544633]
  We consider complex exploration problems, where each agent faces the same (but unknown) MDP. Agents control the choice of policies, whereas an algorithm can only issue recommendations. We design an algorithm which explores all reachable states in the MDP.
  arXiv  Detail & Related papers  (2021-02-28T00:15:53Z)
• Asynchronous Multi Agent Active Search [6.587280549237275]
  We propose two distinct active search algorithms called SPATS (Sparse Parallel Asynchronous Thompson Sampling) and LATSI (LAplace Thompson Sampling with Information gain) We consider that targets are sparsely located around the environment in keeping with compressive sensing assumptions. We provide simulation results as well as theoretical analysis to demonstrate the efficacy of our proposed algorithms.
  arXiv  Detail & Related papers  (2020-06-25T22:17:20Z)

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.