This master’s thesis investigates how modifications of a graph-based map affect multi-agent path planning. We used an existing planner that computes paths and time schedules while accounting for edge and node occupancy caused by other agents. From the realized plans, we derived metrics describing node visits, waiting, edge occupancy, and directional traffic flow. The effect of agent interactions was evaluated by comparing baseline planning on an empty map with interactive planning in the presence of other agents. Spatial and temporal visualizations were used to select map modifications, which were then evaluated through paired A/B experiments with identical task streams. The modifications included adding and directing edges, restricting waiting, subdividing edges, and combining several interventions. With four agents and randomly assigned tasks, bidirectional circular routes reduced total interactive duration by 6.6% and interaction time by 18.2%; directing selected edges increased interactive duration by 32.5%. Across five repetitions with different random seeds, total interactive duration was reduced by an average of 7.18%, with a standard deviation of 0.67 percentage points. For two source–destination task distributions, two added roads reduced interactive duration by 6.4% and 7.4%, respectively. Load tests further showed that the effect of a modification depends on system load. Bidirectional circular routes shifted the first observed saturation level from 10 to 12 agents and achieved 888 instead of 786 tasks per hour with 20 agents under a constant task backlog. The results demonstrate that improving a local traffic metric does not necessarily improve the complete system; each modification must be evaluated for the specific map, planner, task distribution, and load level.
|
