Decentralized Social Navigation with Non-Cooperative Robots via Bi-Level Optimization

• URL: http://arxiv.org/abs/2306.08815v1
• Date: Thu, 15 Jun 2023 02:18:21 GMT
• Title: Decentralized Social Navigation with Non-Cooperative Robots via Bi-Level Optimization
• Authors: Rohan Chandra, Rahul Menon, Zayne Sprague, Arya Anantula, Joydeep Biswas
• Abstract summary: This paper presents a fully decentralized approach for realtime non-cooperative multi-robot navigation in social mini-games. Our contribution is a new realtime bi-level optimization algorithm, in which the top-level optimization consists of computing a fair and collision-free ordering. We successfully deploy the proposed algorithm in the real world using F$1/10$ robots, a Clearpath Jackal, and a Boston Dynamics Spot.
• Score: 11.638394339813154
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper presents a fully decentralized approach for realtime non-cooperative multi-robot navigation in social mini-games, such as navigating through a narrow doorway or negotiating right of way at a corridor intersection. Our contribution is a new realtime bi-level optimization algorithm, in which the top-level optimization consists of computing a fair and collision-free ordering followed by the bottom-level optimization which plans optimal trajectories conditioned on the ordering. We show that, given such a priority order, we can impose simple kinodynamic constraints on each robot that are sufficient for it to plan collision-free trajectories with minimal deviation from their preferred velocities, similar to how humans navigate in these scenarios. We successfully deploy the proposed algorithm in the real world using F$1/10$ robots, a Clearpath Jackal, and a Boston Dynamics Spot as well as in simulation using the SocialGym 2.0 multi-agent social navigation simulator, in the doorway and corridor intersection scenarios. We compare with state-of-the-art social navigation methods using multi-agent reinforcement learning, collision avoidance algorithms, and crowd simulation models. We show that $(i)$ classical navigation performs $44\%$ better than the state-of-the-art learning-based social navigation algorithms, $(ii)$ without a scheduling protocol, our approach results in collisions in social mini-games $(iii)$ our approach yields $2\times$ and $5\times$ fewer velocity changes than CADRL in doorways and intersections, and finally $(iv)$ bi-level navigation in doorways at a flow rate of $2.8 - 3.3$ (ms)$^{-1}$ is comparable to flow rate in human navigation at a flow rate of $4$ (ms)$^{-1}$.

Related papers

• Neural Nonmyopic Bayesian Optimization in Dynamic Cost Settings [73.44599934855067]
  LookaHES is a nonmyopic BO framework designed for dynamic, history-dependent cost environments.<n>LookaHES combines a multi-step variant of $H$-Entropy Search with pathwise sampling and neural policy optimization.<n>Our innovation is the integration of neural policies, including large language models, to effectively navigate structured, domain-specific action spaces.
  arXiv  Detail & Related papers  (2026-01-10T09:49:45Z)
• Flow-Opt: Scalable Centralized Multi-Robot Trajectory Optimization with Flow Matching and Differentiable Optimization [2.4149533870085174]
  Flow-Opt is a learning-based approach towards improving the computational tractability of centralized multi-robot trajectory optimization.<n>We show that we can generate trajectories of tens of robots in cluttered environments in a few tens of milliseconds.<n>Our approach also generates smoother trajectories orders of magnitude faster than competing baselines.
  arXiv  Detail & Related papers  (2025-10-10T09:43:18Z)
• Multi-robot Path Planning and Scheduling via Model Predictive Optimal Transport (MPC-OT) [5.013737017051114]
  We consider a setup where $M robots are tasked to navigate to $M targets in a common space with deadlock obstacles.<n>We derive a strategy based on optimal plannings and guarantee non-overlapping trajectories.<n>We show that a temporal structure can be integrated into optimal transport with the help of textitremodelplans and textitremodelplans as predictive.
  arXiv  Detail & Related papers  (2025-08-28T20:47:33Z)
• Parametrized Multi-Agent Routing via Deep Attention Models [1.0377683220196872]
  We propose a scalable deep learning framework for parametrized sequential decision-making (ParaSDM)<n>A key subclass of this setting is Facility-Location and Pathity (FLPO), where multi-agent systems must simultaneously determine optimal routes and locations.<n>To address this, we integrate Maximum Entropy Principle (MEP) with a neural policy model called the Shortest Path Network (SPN)
  arXiv  Detail & Related papers  (2025-07-30T02:46:45Z)
• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  We present a $textbfMA-OSMA$ algorithm to transfer the discrete submodular problem into a continuous optimization. We also introduce a projection-free $textbfMA-OSEA$ algorithm, which effectively utilizes the KL divergence by mixing a uniform distribution. Our algorithms significantly improve the $(frac11+c)$-approximation provided by the state-of-the-art OSG algorithm.
  arXiv  Detail & Related papers  (2025-02-07T15:57:56Z)
• Fast and scalable Wasserstein-1 neural optimal transport solver for single-cell perturbation prediction [55.89763969583124]
  Optimal transport theory provides a principled framework for constructing such mappings. We propose a novel optimal transport solver based on Wasserstein-1. Our experiments demonstrate that the proposed solver can mimic the $W$ OT solvers in finding a unique and monotonic" map on 2D datasets.
  arXiv  Detail & Related papers  (2024-11-01T14:23:19Z)
• Communication- and Computation-Efficient Distributed Decision-Making in Multi-Robot Networks [2.8936428431504164]
  We provide a distributed coordination paradigm that enables scalable and near-optimal joint motion planning among multiple robots. Our algorithm is up to two orders faster than competitive near-optimal algorithms. In simulations of surveillance tasks with up to 45 robots, it enables real-time planning at the order of 1 Hz with superior coverage performance.
  arXiv  Detail & Related papers  (2024-07-15T01:25:39Z)
• Progressive Entropic Optimal Transport Solvers [33.821924561619895]
  We propose a new class of EOT solvers (ProgOT) that can estimate both plans and transport maps. We provide experimental evidence demonstrating that ProgOT is a faster and more robust alternative to standard solvers. We also prove statistical consistency of our approach for estimating optimal transport maps.
  arXiv  Detail & Related papers  (2024-06-07T16:33:08Z)
• Mixed Strategy Nash Equilibrium for Crowd Navigation [0.41942958779358663]
  Game theory provides a framework for the robot to reason about potential cooperation from humans for collision avoidance during path planning. Mixed strategy Nash equilibrium captures the negotiation behavior under uncertainty, making it well suited for crowd navigation. We name our algorithm Bayesian Recursive Nash Equilibrium (BRNE) and develop a real-time model prediction crowd navigation framework.
  arXiv  Detail & Related papers  (2024-03-03T15:30:59Z)
• Best of Both Worlds Guarantees for Smoothed Online Quadratic Optimization [9.449153668916098]
  We study the smoothed online optimization (SOQO) problem where, at each round $t$, a player plays an action $x_t in response to a quadratic hitting cost and an additional squared $ell$-norm cost for switching actions. This problem class has strong connections to a wide range of application domains including smart grid management, adaptive control, and data center management. We present a best-of-both-worlds algorithm that obtains a robust adversarial performance while simultaneously achieving a near-optimal performance.
  arXiv  Detail & Related papers  (2023-10-31T22:59:23Z)
• Learning Regions of Interest for Bayesian Optimization with Adaptive Level-Set Estimation [84.0621253654014]
  We propose a framework, called BALLET, which adaptively filters for a high-confidence region of interest. We show theoretically that BALLET can efficiently shrink the search space, and can exhibit a tighter regret bound than standard BO.
  arXiv  Detail & Related papers  (2023-07-25T09:45:47Z)
• Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
  We propose a new reward-free algorithm for learning linear Markov decision processes (MDPs) At the core of our algorithm is uncertainty-weighted value-targeted regression with exploration-driven pseudo-reward. We show that our algorithm only needs to explore $tilde O( d2varepsilon-2)$ episodes to find an $varepsilon$-optimal policy.
  arXiv  Detail & Related papers  (2023-03-17T17:53:28Z)
• Two Losses Are Better Than One: Faster Optimization Using a Cheaper Proxy [6.170898159041277]
  We present an algorithm for minimizing an objective with hard-to-compute gradients by using a related, easier-to-access function as a proxy. Our algorithm guarantees convergence at a rate matching the gradient descent on a $delta$-smooth objective. Our algorithm has many potential applications in machine learning, and provides a principled means of leveraging synthetic data, physics simulators, mixed public and private data, and more.
  arXiv  Detail & Related papers  (2023-02-07T15:50:49Z)
• Matching Pursuit Based Scheduling for Over-the-Air Federated Learning [67.59503935237676]
  This paper develops a class of low-complexity device scheduling algorithms for over-the-air learning via the method of federated learning. Compared to the state-of-the-art proposed scheme, the proposed scheme poses a drastically lower efficiency system. The efficiency of the proposed scheme is confirmed via experiments on the CIFAR dataset.
  arXiv  Detail & Related papers  (2022-06-14T08:14:14Z)
• Adaptive Multi-Goal Exploration [118.40427257364729]
  We show how AdaGoal can be used to tackle the objective of learning an $epsilon$-optimal goal-conditioned policy. AdaGoal is anchored in the high-level algorithmic structure of existing methods for goal-conditioned deep reinforcement learning.
  arXiv  Detail & Related papers  (2021-11-23T17:59:50Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary. Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
  arXiv  Detail & Related papers  (2021-06-02T22:03:36Z)
• T$^{\star}$-Lite: A Fast Time-Risk Optimal Motion Planning Algorithm for Multi-Speed Autonomous Vehicles [0.860255319568951]
  T$star$-Lite is a significantly faster version of the previously developed Tstar$ algorithm. T$star$-Lite is developed using the RRT$star$ motion planner.
  arXiv  Detail & Related papers  (2020-08-29T20:25:43Z)

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.