The setting is a team of autonomous mobile agents, motivated by applications such as hospital robots, warehouse systems, package-delivery drones, surveillance, and logistics. Agents operate with uncertain transitions and must avoid collisions with other agents and obstacles while completing tasks effectively. The paper focuses on homogeneous agents pursuing homogeneous objectives, with a common policy learned centrally and applied across the team. In the described experiments, agents move in a two-dimensional grid and may not know the goal location in advance. The supplied excerpt does not establish how the method behaves with sensor noise, communication failures, dynamic obstacles, or physical robot constraints.
The first contribution is a weighted-automaton representation of trajectory-level objectives. Instead of expressing success only as reaching a goal before a deadline, the automaton can assign higher value to trajectories that accomplish the task more expeditiously. The second contribution is MAPF-EGT, an evolutionary-game-theory-based learning algorithm for homogeneous multi-agent teams that uses shared agent experiences and policy updates. The paper reports nearly a 30% reduction in path length in large spaces relative to the evaluated reinforcement-learning methods and at least an order-of-magnitude faster computation than deep RL. It also reports better scaling as the number of agents increases, although the excerpt does not provide the complete numerical breakdown behind these comparisons.
The multi-agent problem is formulated using stochastic games, in which each agent has states, available actions, transition dynamics, and rewards. A common weighted automaton specifies the task for every agent, and the weight accumulated along an agent trajectory represents how well that trajectory satisfies the objective. For reach-avoid tasks, the reward structure distinguishes reaching the goal from colliding with an obstacle and is designed so that, among collision-free trajectories, earlier arrival receives greater value. This is motivated by a limitation of integral-style robustness measures: an agent that reaches a goal quickly and then leaves it can receive less cumulative value than an agent that takes a longer route and remains at the goal. Agents are trained centrally under a shared policy, so experiences from multiple agents can be pooled. Evolutionary-game-based updates modify the stochastic action distribution using generated trajectories, with the intention of improving team behavior through shared and increasingly diverse experience.
The experiments use a two-dimensional grid world. Each agent has five actions—up, down, left, right, and stay—and begins an episode at a random start location, with the requirement to reach one of the goal locations by the end of the episode. Grid sizes include 20 by 20, 50 by 50, 100 by 100, 150 by 150, and 200 by 200. The number of agents is varied across experiments; the experimental description states a range from 2 to 50, while the results discussion describes a test from 2 to 100 agents on a 100 by 100 grid, so the supplied excerpt contains two different range statements. MAPF-EGT is compared with a heuristic planning method, a Monte Carlo method, tabular Q-learning, and PPO. Manhattan distance is used as the heuristic, while the other approaches use the same reward function as the proposed method. Reported measures include time to reach the goal, distance from obstacles, clock time, total time, and computation as the number of agents grows. The implementation uses OpenAI Gym and Stable-Baselines3 PPO, and the experiments run on a laptop with a 2.0 GHz dual-core Intel Core i5 processor and 16 GB of RAM.
The main conceptual advantage is that weighted automata make the quality of an entire trajectory explicit rather than relying only on a myopic state reward. This can reduce a mismatch between what a metric measures and what a reach-avoid task requires: quick, safe completion rather than persistence near a goal. The authors interpret the strong scaling of MAPF-EGT as a consequence of additional agents generating more trajectories and therefore richer, more diverse data for learning. The approach also trades generality for a simpler learning problem by assuming homogeneous agents and objectives and by sharing one policy. Its empirical claims are limited to the reported discrete grid-world setting; the supplied excerpt does not establish collision-success rates, statistical variation, convergence guarantees, communication costs, or behavior under changing environments. The balance between centralized training, shared experience, and execution is not fully specified in the supplied material.
Classical multi-agent path finding commonly uses graph search and combinatorial-optimization heuristics to route agents to assigned goals without collisions. Reinforcement-learning approaches can learn behavior from state-based or user-specified rewards, but short-horizon rewards may encourage undesirable long-term behavior, including reward hacking. Automata-based specifications, temporal logic, robustness measures, and non-Markovian reward models have therefore been explored for tasks whose value depends on history and time. Weighted automata extend this direction by associating transition weights with an accepting task structure.
The problem is to synthesize policies for multiple agents that reach goals safely and efficiently under uncertain transitions. A binary success signal is insufficient when successful trajectories differ in arrival time, path length, or safety-related behavior. A useful specification must capture both whether the task is completed and how well the complete trajectory satisfies the intended temporal objective. The agents may also need to learn without prior knowledge of the goal location.
A weighted automaton is a finite-state task model with accepting conditions and weights on transitions. The proposed reward construction gives special treatment to goal-reaching transitions and obstacle collisions, and the paper states that faster collision-free goal-reaching trajectories obtain higher automaton rewards. The policy is stochastic, with action probabilities updated from shared experience under centralized training. The supplied excerpt mentions a complexity analysis but does not preserve enough notation or parameter definitions to establish the exact complexity expression or update schedule.
The action set is up, down, left, right, and stay in a two-dimensional grid. Episodes use random initial locations and require an agent to reach a goal location, while grid size and team size are varied. Baselines include a heuristic search planner, Monte Carlo, tabular Q-learning, and PPO; the heuristic uses Manhattan distance, and the other methods use the proposed reward structure. The reported implementation uses OpenAI Gym and Stable-Baselines3, running on a 2.0 GHz dual-core Intel Core i5 laptop with 16 GB of memory.
The paper reports that MAPF-EGT reduces path length by nearly 30% in large spaces compared with the evaluated reinforcement-learning methods. It is reported to be at least an order of magnitude faster computationally than deep RL and to have computation time comparable to the Monte Carlo method. Q-learning is described as having training and scalability difficulties for large grids, although its short run time makes its scaling with agent count relatively steady. PPO scales poorly as the number of agents increases, whereas MAPF-EGT is reported to scale best. The excerpt does not include exact values for every grid size, repetitions, confidence intervals, or success-rate comparisons.
The paper presents a way to combine trajectory-level weighted-automaton objectives with evolutionary-game-based learning for multi-agent path finding. Within the reported grid-world experiments, MAPF-EGT is claimed to improve path efficiency and computation time while scaling favorably with more agents. These findings suggest that explicit temporal reward structure and shared experience can complement conventional reinforcement learning and heuristic planning.
The current formulation is restricted to discrete state and action spaces. The authors propose extending it to continuous spaces using radial-basis-function approximation for nearby states, probability-density-function updates, and Dirac-delta-based adjustments. The current study also assumes homogeneous agents and homogeneous tasks, and future work is intended to address more diverse multi-agent learning and convergence guarantees. Game-theoretic guarantees for robust strategic interactions are proposed as another future direction. The supplied excerpt does not establish formal safety guarantees or validation in continuous, physical, or dynamically changing environments.
The work is relevant because it reframes MAPF as a trajectory-quality problem rather than only a collision-free shortest-path problem. Its weighted-automaton formulation offers a way to encode timeliness and expeditiousness, while MAPF-EGT offers a shared-policy learning mechanism for homogeneous teams. If the reported improvements generalize beyond the tested grids, the approach could be useful for large teams with common objectives. That generalization remains unestablished by the supplied excerpt.
This paper is suitable for researchers studying timed or history-dependent MAPF objectives, automata-based reinforcement learning, reward design, and evolutionary approaches to multi-agent learning. It is especially relevant for readers interested in centralized training and shared policies for homogeneous agents. Readers seeking results for heterogeneous teams, continuous control, formal safety guarantees, or realistic communication and sensing constraints will need additional evidence beyond the supplied excerpt.