Multi-Robot Searching using Game-Theory Based Approach

This paper proposes a game-theory based approach in a multi–target searching using a multi-robot system in a dynamic environment. It is assumed that a rough priori probability map of the targets' distribution within the environment is given. To consider the interaction between the robots, a dynamic-programming equation is proposed to estimate the utility function for each robot. Based on this utility function, a cooperative nonzero-sum game is generated, where both pure Nash Equilibrium and mixed-strategy Equilibrium solutions are presented to achieve an optimal overall robot behaviors. A special consideration has been taken to improve the real-time performance of the game-theory based approach. Several mechanisms, such as event-driven discretization, one-step dynamic programming, and decision buffer, have been proposed to reduce the computational complexity. The main advantage of the algorithm lies in its real-time capabilities whilst being efficient and robust to dynamic environments.

• Publication year

  2008

• Venue

  International Journal of Advanced Robotic Systems

• Publication date

  2008-11-01

• Fields of study

  Computer Science, Engineering

• Identifiers
  DOI 10.5772/6232
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Search for dynamic targets with uncertain probability maps

  2006cited by this paper
• Robust UAV Search for Environments with Imprecise Probability Maps

  2005cited by this paper
• Optimal search for multiple targets in a built environment

  2005cited by this paper
• Game theory based target following by a team of robots

  2004cited by this paper
• Coordinated decentralized search for a lost target in a Bayesian world

  2003cited by this paper
• Cooperative real-time search and task allocation in UAV teams

  2003cited by this paper
• Multi-robot decision making using coordination graphs

  2003cited by this paper
• Probabilistic pursuit-evasion games: theory, implementation, and experimental evaluation

  2002cited by this paper
• Online Parallel Heuristics and Robot Searching under the Competitive Framework

  2002cited by this paper
• Probabilistic pursuit-evasion games: a one-step Nash approach

  2000cited by this paper
• Monte Carlo Localization: Efficient Position Estimation for Mobile Robots

  1999cited by this paper
• Searching in an unknown environment: an optimal randomized algorithm for the cow-path problem

  1996cited by this paper
• Path selection and coordination for multiple robots via Nash equilibria

  1994cited by this paper
• Searching in the Plane

  1993cited by this paper
• An Optimal Branch-and-Bound Procedure for the Constrained Path, Moving Target Search Problem

  1990cited by this paper
• Общая теория выбора равновесия в играх / A General Theory of Equilibrium Selection in Games

  1989cited by this paper
• The Optimal Search for a Moving Target When the Search Path Is Constrained

  1984cited by this paper
• Search for a moving target when searcher motion is restricted

  1979cited by this paper

• Game-Theoretic Autonomous Vehicle Path Coordination with Limited Communication

  2025cites this paper
• A Game of Social Forces: Integrating Non-cooperative Game Theory with Social Force Model for a Socially-acceptable Mobile Robot Navigation

  2025cites this paper
• A Potential Game with a Dynamic Penalization Map for Multi-Robot Cooperative Search Missions

  2024cites this paper
• Strategic Control Against an Intruder for Timely and Accurate Updates to a Reactive Receiver

  2024cites this paper
• Nash Equilibrium Seeking for Multi-Agent Systems Under DoS Attacks and Disturbances

  2024cites this paper
• Joint SLAM and Joint Search of Unmanned Car Cluster

  2023cites this paper
• Game theory approaches for autonomy

  2022cites this paper
• Multi Robot Surveillance and Planning in Limited Communication Environments

  2022cites this paper
• Evaluating pedestrian interaction preferences with a game theoretic autonomous vehicle in virtual reality

  2021cites this paper
• Analytical and experimental nonzero-sum differential game-based control of a 7-DOF robotic manipulator

  2021cites this paper
• Adversarial Planning for Multi-Agent Pursuit-Evasion Games in Partially Observable Euclidean Space

  2021cites this paper
• Joint Task Assignment and Trajectory optimization for a Mobile Robot Swarm by Mean-Field Game

  2020cites this paper
• Game Theoretic Decentralized and Communication-Free Multi-Robot Navigation

  2020cites this paper
• Context-Aware Deep Q-Network for Decentralized Cooperative Reconnaissance by a Robotic Swarm

  2020cites this paper
• Decentralized and Communication-Free Multi-Robot Navigation through Distributed Games

  2020cites this paper
• Teaching robots to imitate a human with no on-teacher sensors. What are the key challenges?

  2019cites this paper
• Decision Making for Autonomous Vehicles at Unsignalized Intersection in Presence of Malicious Vehicles

  2019cites this paper
• Human-like Motion Planning in Populated Environments

  2019cites this paper
• Human-Like Motion Planning Based on Game Theoretic Decision Making

  2018cites this paper
• Persistent Monitoring with Energy-Limited Unmanned Aerial Vehicles Assisted by Mobile Recharging Stations

  2018cites this paper
• Two-agent cooperative search model with Petri nets

  2018cites this paper
• Optimal control of multiple quadrotors for transporting a cable suspended payload

  2018cites this paper
• Modelling and analysis of information-based target searching using mobile sensors

  2018cites this paper
• Connecting the Autonomous: A Distributed Game Theory Approach for VANET Connectivity

  2017cites this paper
• Enhancing VANET connectivity through utilizing autonomous vehicles

  2017cites this paper
• Application of game theory in path planning of multiple robots

  2017cites this paper
• Improving Resilience of Autonomous Moving Platforms by Real Time Analysis of Their Cooperation

  2017cites this paper
• Modeling and Analysis of Grid-Based Target Searching Problems in a Mobile Sensor Network

  2017cites this paper
• Multi-agent target searching with time constraints using game-theoretic approaches

  2017cites this paper
• Strategies for searching a mobile target using mobile sensors in a two-dimensional grid

  2017cites this paper
• A Strategic Framework for Searching Mobile Targets Using Mobile Sensors

  2017cites this paper
• Vers une interaction humain-robot à une initiative mixe : une équipe coopérative composée par des drones et un opérateur humain

  2017cites this paper
• DECISION SUPPORT FOR WIRELESS EVNIRONMENTS WITH APPLICATIONS TO RADAR SYSTEMS

  2017cites this paper
• Strategies for Searching Targets Using Mobile Sensors in Defense Scenarios

  2017cites this paper
• Understanding Human Avoidance Behavior: Interaction-Aware Decision Making Based on Game Theory

  2016cites this paper
• A Game Theoretical Formulation of a Decentralized Cooperative Multi-Agent Surveillance Mission

  2016cites this paper
• Game Theory and Its Applications in Machine Learning

  2016cites this paper
• Multiagent Cooperative Learning Strategies for Pursuit-Evasion Games

  2015cites this paper
• Models for autonomous robot interactions in a dynamic environment

  2015cites this paper
• Using Cognitive Behavioral Learning in Multi-agent Pursuit-Evasion Game

  2014cites this paper
• Experimental Validation of Patrolling Strategies in an Automated Surveillance Environment

  2014cites this paper
• Handling uncertainty of resource division in multi agent system using game against nature

  2014cites this paper
• Internet Appendix A 1 : Illustrative Pitch Examples in Finance

  2014cites this paper
• Multi-robot Task Planning Problem with Uncertainty in Game Theoretic Framework

  2013cites this paper
• A game theoretic framework for incentive-based models of intrinsic motivation in artificial systems

  2013cites this paper
• Essential Principles for Autonomous Robotics

  2013cites this paper
• Generating strategies for multi-agent pursuit-evasion games in partially observable Euclidean space

  2012cites this paper
• Toward Opportunistic Collaboration in Target Pursuit Problems

  2011cites this paper
• QUERY PROCESSING FOR PROBABILISTIC STATE DIAGRAMS DESCRIBING MULTIPLE ROBOT NAVIGATION IN AN INDOOR ENVIRONMENT

  2011cites this paper
• Use of Multi-level State Diagrams for Robot Cooperation in an Indoor Environment

  2011cites this paper
• Strategy generation in multi-agent imperfect-information pursuit games

  2010cites this paper