Asynchronous Multi Agent Active Search

• URL: http://arxiv.org/abs/2006.14718v1
• Date: Thu, 25 Jun 2020 22:17:20 GMT
• Title: Asynchronous Multi Agent Active Search
• Authors: Ramina Ghods, Arundhati Banerjee, Jeff Schneider
• Abstract summary: 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.
• Score: 6.587280549237275
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Active search refers to the problem of efficiently locating targets in an unknown environment by actively making data-collection decisions, and has many applications including detecting gas leaks, radiation sources or human survivors of disasters using aerial and/or ground robots (agents). Existing active search methods are in general only amenable to a single agent, or if they extend to multi agent they require a central control system to coordinate the actions of all agents. However, such control systems are often impractical in robotics applications. In this paper, we propose two distinct active search algorithms called SPATS (Sparse Parallel Asynchronous Thompson Sampling) and LATSI (LAplace Thompson Sampling with Information gain) that allow for multiple agents to independently make data-collection decisions without a central coordinator. Throughout we consider that targets are sparsely located around the environment in keeping with compressive sensing assumptions and its applicability in real world scenarios. Additionally, while most common search algorithms assume that agents can sense the entire environment (e.g. compressive sensing) or sense point-wise (e.g. Bayesian Optimization) at all times, we make a realistic assumption that each agent can only sense a contiguous region of space at a time. We provide simulation results as well as theoretical analysis to demonstrate the efficacy of our proposed algorithms.

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)
• Decentralized Multi-Agent Active Search and Tracking when Targets Outnumber Agents [8.692007892160913]
  We propose a decentralized multi-agent, multi-target, simultaneous active search-and-tracking algorithm called DecSTER. Our proposed algorithm uses a sequential monte carlo implementation of the probability hypothesis density filter for posterior inference combined with Thompson sampling for decentralized multi-agent decision making. In simulation, we demonstrate that DecSTER is robust to unreliable inter-agent communication and outperforms information-greedy baselines in terms of the Optimal Sub-Pattern Assignment (OSPA) metric.
  arXiv  Detail & Related papers  (2024-01-06T08:10:58Z)
• AI planning in the imagination: High-level planning on learned abstract search spaces [68.75684174531962]
  We propose a new method, called PiZero, that gives an agent the ability to plan in an abstract search space that the agent learns during training. We evaluate our method on multiple domains, including the traveling salesman problem, Sokoban, 2048, the facility location problem, and Pacman.
  arXiv  Detail & Related papers  (2023-08-16T22:47:16Z)
• 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 Deep Covering Skill Discovery [50.812414209206054]
  We propose Multi-agent Deep Covering Option Discovery, which constructs the multi-agent options through minimizing the expected cover time of the multiple agents' joint state space. Also, we propose a novel framework to adopt the multi-agent options in the MARL process. We show that the proposed algorithm can effectively capture the agent interactions with the attention mechanism, successfully identify multi-agent options, and significantly outperforms prior works using single-agent options or no options.
  arXiv  Detail & Related papers  (2022-10-07T00:40:59Z)
• Cost Aware Asynchronous Multi-Agent Active Search [6.587280549237275]
  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.
  arXiv  Detail & Related papers  (2022-10-05T13:38:30Z)
• 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)
• Cooperative Exploration for Multi-Agent Deep Reinforcement Learning [127.4746863307944]
  We propose cooperative multi-agent exploration (CMAE) for deep reinforcement learning. The goal is selected from multiple projected state spaces via a normalized entropy-based technique. We demonstrate that CMAE consistently outperforms baselines on various tasks.
  arXiv  Detail & Related papers  (2021-07-23T20:06:32Z)
• Multi-Agent Active Search using Realistic Depth-Aware Noise Model [8.520962086877548]
  Active search for objects of interest in an unknown environment has many robotics applications including search and rescue, detecting gas leaks or locating animal poachers. Existing algorithms often prioritize the location accuracy of objects of interest while other practical issues such as the reliability of object detection as a function of distance and lines of sight remain largely ignored. We present an algorithm called Noise-Aware Thompson Sampling (NATS) that addresses these issues for multiple ground-based robots performing active search considering two sources of sensory information from monocular optical imagery and depth maps.
  arXiv  Detail & Related papers  (2020-11-09T23:20:55Z)
• Never Give Up: Learning Directed Exploration Strategies [63.19616370038824]
  We propose a reinforcement learning agent to solve hard exploration games by learning a range of directed exploratory policies. We construct an episodic memory-based intrinsic reward using k-nearest neighbors over the agent's recent experience to train the directed exploratory policies. A self-supervised inverse dynamics model is used to train the embeddings of the nearest neighbour lookup, biasing the novelty signal towards what the agent can control.
  arXiv  Detail & Related papers  (2020-02-14T13:57:22Z)

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.