skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Bounded-Rational Pursuit-Evasion Games
We present a framework that incorporates the principle of bounded rationality into dynamic stochastic pursuit-evasion games. The solution of a stochastic game is generally characterized by its (Nash) equilibria in feedback form, whose calculation may require extensive computational resources. In this paper, the agents are modeled as bounded rational entities with limited computational capabilities. We illustrate the proposed framework by applying it to a pursuit-evasion game between two aerial vehicles in a stochastic wind field. We show how such a game may be discretized and properly analyzed by casting it as an iterative sequence of finite-state Markov Decision Processes (MDPs). Leveraging tools and algorithms from the cognitive hierarchy theory (“level-k thinking”) we compute the solution of the ensuing discrete game, while taking into consideration the rationality level of each agent. We also present an online algorithm for each agent to infer its opponent's rationality level.  more » « less
Award ID(s):
1849130
PAR ID:
10315945
Author(s) / Creator(s):
; ; ;
Date Published:
Journal Name:
American Control Conference
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, AIAA SciTech Forum, Guidance, Navigation, and Control)
    In this paper, pursuit-evasion scenarios in a stochastic flow field involving one pursuer and one evader are analyzed. Using a forward reachability set-based approach and the associated level set equations, nominal solutions of the players are generated. The dynamical system is linearized along the nominal solution to formulate a chance-constrained, linear-quadratic stochastic dynamic game. Assuming an affine disturbance feedback structure, the proposed game is solved using the standard Gauss-Seidel iterative scheme. Numerical simulations demonstrate the proposed approach for realistic flow fields. 
    more » « less
  2. ; ; ; (, Proceedings of the Design Society)
    Rational decision-making is crucial in the later stages of engineering system design to allocate resources efficiently and minimize costs. However, human rationality is bounded by cognitive biases and limitations. Understanding how humans deviate from rationality is critical for guiding designers toward better design outcomes. In this paper, we quantify designer rationality in competitive scenarios based on utility theory. Using an experiment inspired by crowd-sourced contests, we show that designers employ varied search strategies. Some participants approximate a Bayesian agent that aimed to maximize its expected utility. Those with higher rationality reduce uncertainty more effectively. Furthermore, rationality correlates with both the proximity to optimal design and design iteration costs, with winning participants exhibiting greater rationality than losing participants. 
    more » « less
  3. ; ; ; (, IEEE International Conference on Robotics and Automation)
    null (Ed.)
    Given a two-dimensional polygonal space, the multi-robot visibility-based pursuit-evasion problem tasks several pursuer robots with the goal of establishing visibility with an arbitrarily fast evader. The best known complete algorithm for this problem takes time doubly exponential in the number of robots. However, sampling-based techniques have shown promise in generating feasible solutions in these scenarios. One of the primary drawbacks to employing existing sampling-based methods is that existing algorithms have long execution times and high failure rates for complex environments. This paper addresses that limitation by proposing a new algorithm that takes an environment as its input and returns a joint motion strategy which ensures that the evader is captured by one of the pursuers. Starting with a single pursuer, we sequentially construct Sample-Generated Pursuit-Evasion Graphs to create such a joint motion strategy. This sequential graph structure ensures that our algorithm will always terminate with a solution, regardless of the complexity of the environment. We describe an implementation of this algorithm and present quantitative results that show significant improvement in comparison to the existing algorithm. 
    more » « less
  4. ; ; ; (, IEEE)
    This paper introduces and solves a visibility-based escort planning problem. This novel problem, which is closely related to the well-researched family of visibility-based pursuit-evasion problems in robotics, entails an escort agent tasked with escorting a vulnerable agent, called the VIP, in a 2-dimensional environment. The escort protects the VIP from adversaries that pose line-of-sight threats. We describe a correct and complete planning algorithm whose inputs are a simply-connected polygonal map of the environment, starting locations for the escort and the VIP, along with a goal location to which the VIP agent should be safely moved. The algorithm computes trajectories for the escort and VIP which allow the VIP to reach its goal without coming into the line-of-sight of the adversary at any time. During the execution of these trajectories, the adversary is allowed to move along any continuous path that does not enter into the line-of-sight of the escort. The algorithm proceeds by dividing the environment into a collection of conservative regions and planning the escort's movements as a sequence of these regions via breadth-first search over an information graph. The trajectory of the VIP can then be constructed by tracing the 'safe zones' swept out by the escort's trajectory. We describe an implementation of this algorithm and present computed examples of escort agent strategies in diverse environments. 
    more » « less
  5. ; ; ; ; ; ; ; (, International Symposium on Combinatorial Search)
    null (Ed.)
    The Multi-Agent Path Finding (MAPF) problem arises in many real-world applications, ranging from automated warehousing to multi-drone delivery. Solving the MAPF problem optimally is NP-hard, and existing optimal and bounded-suboptimal MAPF solvers thus usually do not scale to large MAPF instances. Greedy MAPF solvers scale to large MAPF instances, but their solution qualities are often bad. In this paper, we therefore propose a novel MAPF solver, Hierarchical Multi-Agent Path Planner (HMAPP), which creates a spatial hierarchy by partitioning the environment into multiple regions and decomposes a MAPF instance into smaller MAPF sub-instances for each region. For each sub-instance, it uses a bounded-suboptimal MAPF solver to solve it with good solution quality. Our experimental results show that HMAPP solves as large MAPF instances as greedy MAPF solvers while achieving better solution qualities on various maps. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email