Evolutionary synthesis of multi-agent systems for dynamic dial-a-ride problems

Rinde R. S. van Lon, Tom Holvoet, Greet Vanden Berghe, Tom Wenseleers, Jürgen BrankeGECCO (Companion) 2012 · DOI

TL;DR

This paper explores using genetic programming (GP) to automatically design decentralized multi-agent systems (MAS) for dynamic dial-a-ride problems (DARP). The authors demonstrate that GP can evolve effective agent decision-making heuristics, outperforming a sophisticated hyper-heuristic and offering a viable alternative to manual MAS design.

What Problem Does This Paper Address?

The dynamic dial-a-ride problem (DARP) involves a fleet of vehicles needing to fulfill transportation requests that arrive over time, with each request having a pickup location, drop-off location, and a deadline. This is a complex optimization challenge, especially in real-world scenarios where requests are unpredictable. Traditional approaches often rely on centralized systems or hand-designed decentralized agents. Hand-designing decentralized MAS for such dynamic problems is difficult because agents must make decisions based on local, incomplete information while still aiming for a global objective (minimizing overall tardiness). This paper investigates whether genetic programming can automate the creation of these crucial agent decision-making heuristics, thereby simplifying the design of effective decentralized MAS for dynamic DARPs.

Methods

The core of this research lies in using genetic programming (GP) to evolve the decision-making logic for individual agents (vehicles) in a multi-agent system. Each agent's "brain" is represented as a program, specifically a syntax tree, which calculates a priority value for each available request. Agents then choose to serve the request with the highest priority.

  • GP Representation: The evolved heuristics are functions that take an agent and a request as input and output a priority value. These functions are represented as trees, where nodes are operations (like mathematical operators, conditional logic) and leaves are terminals (variables like distance, time left, or constants).
  • Simulation-Based Fitness: Since the quality of a heuristic cannot be easily determined analytically, the fitness of each evolved program is evaluated through simulations. The MAS is run on a discrete event simulator (RinSim) for a given scenario, and the system's performance (total tardiness) is measured.
  • Decentralized MAS: The MAS is inherently decentralized, with each vehicle acting as an autonomous agent. Agents make decisions based on their local perception and the evolved heuristic. Conflicts (multiple agents targeting the same request) are resolved by the agent that arrives first.
  • Comparison: The evolved MAS is compared against two baselines:
  • A centralized static solution (lower bound, knows all requests beforehand).
  • A centralized dynamic hyper-heuristic (uses a rolling-time horizon, optimizing based on current information).

Datasets

The paper introduces a new set of scenarios for evaluating DARP solutions. These scenarios are situated on a simplified map of the city of Leuven, Belgium, derived from OpenStreetMap. This differs from many DARP benchmarks that use abstract Euclidean planes, as it incorporates real-world road structures and allows for more realistic vehicle movement and diversion. The authors make their scenarios and map publicly available.

Key Insights and Ideas

  • GP as an Automated Designer: The most significant insight is that genetic programming can effectively automate the design of complex decision-making heuristics for decentralized multi-agent systems, a task that is typically challenging and time-consuming for human designers.
  • Viable Alternative to Manual Design: The results suggest that GP-evolved heuristics can be a practical and powerful alternative to manually crafting agent behaviors for dynamic DARP.
  • Decentralization Works: The research demonstrates that a fully decentralized MAS, guided by evolved heuristics, can achieve competitive performance against more centralized approaches.
  • Surprising Performance of Simpler GP: An unexpected finding was that a GP run with fewer generations (gp 51) performed slightly better than one with more generations (gp 101), suggesting that computational cost doesn't always directly correlate with better solutions and that the search space might have local optima.
  • Distance Heuristic Superiority: Among the simple hand-constructed heuristics, the "distance" heuristic (prioritizing the closest request) performed significantly better than the "timeleft" heuristic (prioritizing the most urgent). However, both were substantially outperformed by the GP-evolved heuristics.

Key Results

The GP-evolved MAS consistently outperformed the dynamic variant of the selection hyper-heuristic across all tested scenarios. For instance, the mean ratio of tardiness for the GP-evolved heuristics (gp 51 and gp 101) compared to the hyper-heuristic was significantly lower (around 3.8-17.8 vs. 327.4 for the hyper-heuristic). As expected, the evolved solutions did not surpass the static centralized solution, which serves as a theoretical lower bound. The paper also notes that the GP-evolved heuristics were substantially better than the simple hand-constructed "distance" and "timeleft" heuristics.

Limitations and Future Work

  • Limitations:
    • The GP runs were performed only once due to high computational cost, meaning the results might be sensitive to random chance in the evolutionary process.
  • The current MAS is homogenous, meaning all agents (vehicles) have the same capabilities and use the same evolved heuristic.
  • The current heuristics only plan one request ahead, which might be suboptimal for certain scenarios.
  • Future Work:
    • Communication: Extending the GP to evolve heuristics that incorporate agent communication would allow for better coordination and conflict avoidance.
  • Heterogeneous MAS: Investigating whether a MAS with agents having different characteristics or specializations could lead to improved performance.
  • More Sophisticated Planning: Exploring GP structures that allow for longer-term planning beyond just the next request.

Summary updated

BibTeX
@inproceedings{lon2012evolutionary,
  author = {Rinde R. S. van Lon and Tom Holvoet and Greet Vanden Berghe and Tom Wenseleers and Jürgen Branke},
  title = {{Evolutionary synthesis of multi-agent systems for dynamic dial-a-ride problems}},
  booktitle = {GECCO (Companion)},
  year = {2012},
  doi = {10.1145/2330784.2330832},
}
Figure