Abstract
Effective decision making while competing for limited resources in adversarial environments is important for many real-world applications (e.g. two Taxi companies competing for customers). Decision-making techniques such as Automated planning have to take into account possible actions of adversary (or competing) agents. That said, the agent should know what the competitor will likely do and then generate its plan accordingly. In this paper we propose a novel approach for estimating strategies of the adversary (or the competitor), sampling its actions that might hinder agent's goals by interfering with the agent's actions. The estimated competitor strategies are used in plan generation such that agent's actions have to be applied prior to the ones of the competitor, whose estimated times dictate the deadlines. We empirically evaluate our approach leveraging sampling of competitor's actions by comparing it to the naive approach optimising the make-span (not taking the competing agent into account at all) and to Nash Equilibrium (mixed) strategies.
Introduction: The Challenge of Resource Competition
In many real-world scenarios, agents do not operate in a vacuum. Whether it is rival taxi companies competing for passengers or drone fleets vying for supplies in a disaster zone, the success of a plan often depends on securing limited resources before an opponent does. Standard automated planning typically assumes a static environment where the agent is the sole actor. Ignoring the competition—the "naive" approach—frequently leads to failure because an adversary can snatch a critical resource, rendering the agent's plan unexecutable.
While game theory offers a robust solution through Nash Equilibrium, calculating these strategies in complex planning environments is computationally intensive. The standard "Double Oracle" algorithm requires solving multiple NP-hard planning problems iteratively until convergence, which is often too slow for practical use. This paper introduces a middle ground: an "adversary-aware" planning method that is significantly more efficient than traditional game-theoretic approaches.
Methodology: Strategy Sampling and Deadlines
The core innovation of this research is a two-part heuristic approach designed to estimate an adversary's strategy without the overhead of full game-theoretic optimization. The method reframes competition as a set of probabilistic deadlines.
1. Estimating Action Timing
Inspired by the $h^{max}$ heuristic in classical planning, the authors developed an algorithm to estimate the Earliest Action Application Time. This provides a lower bound for when any given action can be performed by accounting for the time required to satisfy preconditions and the duration of preceding actions.
2. Adversary Strategy Sampling
Rather than attempting to find the single optimal adversary plan, the approach "samples" $k$ plausible plans. Using a roulette-wheel selection process that favors actions with earlier estimated start times, the algorithm creates a "skeleton" of potential opponent behaviors. These samples act as a proxy for the variance of competition.
3. Response Planning
Once the samples are generated, they are treated as a set of deadlines. If the agent's action arrives at a resource after the opponent's sampled time, the agent "loses" that resource and incurs a cost. The agent then solves a single cost-optimal planning task to find the best response to these estimated deadlines. This effectively turns a complex game into a simpler planning problem with temporal constraints.
Evaluation and Results
The approach was tested across two primary domains: Resource Hunting (UAV fleets) and the Taxi Domain (competing for passengers). The benchmarks scaled from simple 1v1 scenarios to larger configurations with multiple agents and resources.
Key Findings
- Computational Efficiency: As shown in Figure 6, the sampling method is dramatically faster than the Double Oracle algorithm, typically providing a speedup of 9x to 53x. The log-scale plots demonstrate that as problem complexity increases, the sampling approach maintains a manageable computational profile compared to the baseline.
- Plan Quality: Plans generated via sampling consistently outperformed naive plans. In most test cases, the utility achieved was remarkably close to the true Nash Equilibrium, suggesting that sampling effectively captures the essential competitive dynamics.
- Robustness: By combining multiple sampled plans into a mixed strategy, the agent's behavior became significantly harder for an adversary to exploit. This unpredictability is a key advantage in adversarial settings.
Conclusion and Future Directions
This research demonstrates that estimating an adversary's strategy through sampling is a viable and efficient alternative to full game-theoretic optimization in resource-competition planning. By focusing on the deadlines imposed by an opponent rather than their entire logic, agents can generate effective plans in a fraction of the time.
However, limitations remain. The current heuristic can underestimate times in domains with strict serial constraints (e.g., one taxi performing multiple sequential trips). Future work will focus on improving these temporal estimates and extending the framework to multi-agent scenarios with more than two players, potentially integrating online adaptation techniques like Monte-Carlo Tree Search.
Summary updated