Generating Motion Patterns Using Evolutionary Computation in Digital Soccer

Masood Amoozgar, Daniel Khashabi, Milad Heydarian, Mohammad Nokhbeh-Zaeem, Saeed Bagheri ShourakiarXiv 2012 · OpenReview

Abstract

Dribbling an opponent player in a digital soccer environment is a critical challenge in motion planning, characterized by complexities inherent to multi-agent systems. This paper proposes a hybrid approach combining computational geometry and evolutionary computation to generate motion trajectories that avoid mobile, adversarial obstacles. By bifurcating the process into an offline optimization stage and an online execution stage, we significantly reduce real-time computational overhead. The offline stage utilizes Genetic Algorithms (GA) to refine trajectory plans, while the online stage employs Delaunay triangulation and linear interpolation for rapid action retrieval.

Introduction

In the domain of multi-agent systems, such as the RoboCup digital soccer environment, motion planning is complicated by the presence of intelligent, adversarial agents. Unlike static obstacle avoidance, a dribbling agent must navigate toward a target while maintaining ball control and evading a defender who actively attempts to intercept. Calculating optimal evasive maneuvers in real-time is computationally intensive, often leading to latency that degrades agent performance.

The digital soccer environment setup involving a dribbling agent, ball, and defender.

To address this, we propose a framework that shifts the heavy computational burden to an offline phase, allowing the agent to execute sophisticated maneuvers using lightweight geometric lookups during live gameplay. This approach ensures that the agent remains responsive even in high-speed, unpredictable scenarios.

Methodology

Our approach is divided into two distinct phases: offline optimization and online execution.

Offline Stage: Evolutionary Optimization

The process begins with a human designer using the "Dribble Editor" (DEdit) tool—a custom Java application—to create an initial "trajectory plan." This plan consists of a network of nodes, each storing data regarding acceleration, body orientation, and ball direction.

To refine this initial intuition, we employ a Genetic Algorithm (GA). The GA operates on a population of trajectory plans, using standard evolutionary operators:

  • Selection: Roulette Wheel selection identifies the most promising candidates.
  • Crossover and Mutation: Standard crossover and Gaussian mutation introduce variation and explore the solution space.
  • Fitness Function: The core of the optimization is a fitness function that balances two competing objectives: straightness (minimizing the path length to the goal to conserve agent stamina) and safety (maximizing the distance between the ball and the defender to prevent interception).

Online Stage: Geometric Execution

During a match, the agent must respond instantly to the defender's position. Instead of re-running the GA, the agent references the pre-optimized trajectory plan. Using Delaunay Triangulation, the agent identifies the relevant triangular region in the $xy$-plane corresponding to its current position relative to the defender. Linear interpolation between the nodes of this triangle then yields the precise acceleration and direction required. This method is computationally efficient ($O(n \log n)$ for triangulation) and allows for smooth, continuous motion without the need for real-time optimization.

Results and Discussion

The Genetic Algorithm successfully optimized the manually designed plans, with mean fitness scores showing a steady upward trend over 250 generations (increasing from approximately 376 to 381). This indicates that the GA effectively refined the human-provided starting points into more efficient and safer trajectories.

Visualization of the emergent motion field around a defender agent.

Qualitative analysis of the resulting motion patterns reveals an emergent "magnetic" evasion behavior. As seen in the motion field visualizations, the agent learns to apply maximum acceleration when in close proximity to the defender, effectively "bursting" past the obstacle. Furthermore, velocity distribution maps indicate that the agent strategically increases speed once it has successfully bypassed the opponent, securing its positional advantage. The resulting trajectories appear remarkably human-like, balancing the need for speed with the necessity of ball protection.

Conclusion

This hybrid approach demonstrates that combining human intuition with evolutionary optimization and geometric interpolation can produce high-quality motion patterns for complex multi-agent tasks. By offloading optimization to a pre-game stage, we ensure high responsiveness in real-time environments. Future work will focus on making the online stage more adaptive to dynamic defender behaviors and incorporating probabilistic models to handle uncertainty in opponent reactions, moving beyond static optimal policies.

Summary updated

Abstract

Dribbling an opponent player in digital soccer environment is an important practical problem in motion planning. It has special complexities which can be generalized to most important problems in other similar Multi Agent Systems. In this paper, we propose a hybrid computational geometry and evolutionary computation approach for generating motion trajectories to avoid a mobile obstacle. In this case an opponent agent is not only an obstacle but also one who tries to harden dribbling procedure. One characteristic of this approach is reducing process cost of online stage by transferring it to offline stage which causes increment in agents' performance. This approach breaks the problem into two offline and online stages. During offline stage the goal is to find desired trajectory using evolutionary computation and saving it as a trajectory plan. A trajectory plan consists of nodes which approximate information of each trajectory plan. In online stage, a linear interpolation along with Delaunay triangulation in xy-plan is applied to trajectory plan to retrieve desired action.
BibTeX
@misc{amoozgar2012generating,
  author = {Masood Amoozgar and Daniel Khashabi and Milad Heydarian and Mohammad Nokhbeh-Zaeem and Saeed Bagheri Shouraki},
  title = {{Generating Motion Patterns Using Evolutionary Computation in Digital Soccer}},
  year = {2012},
  eprint = {1212.6216},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1212.6216},
}
Figure