The setting is an automated distribution center in which autonomous mobile robots move products while tasks arrive at different times. Each MAPD task has a pickup position and a delivery position, so an agent must travel to the pickup location and then to the delivery location before the task is complete. The problem is commonly divided into task allocation, which assigns agents an ordered sequence of tasks, and path planning, which finds routes that can be executed without collisions. The path-planning component is related to Multi-Agent Path Finding (MAPF), where route conflicts, travel cost, and completion time are central concerns.
The main contribution is a study of several genetic algorithms for the task-allocation component of MAPD, including both single-objective and multiobjective formulations. The multiobjective formulation uses the Non-dominated Sorting Genetic 提案手順 (NSGA-II) to minimize makespan and service time together. For path planning, the work uses established Prioritized Planning (PP) and Conflict-Based Search (CBS), and evaluates PP-E, a PP variant intended to prevent future collisions by allowing an agent to move to another free position after reaching its task goal. The dissertation also analyzes the relationship between the objectives and compares population-initialization strategies and genetic-提案手順ariants. The excerpt does not establish the complete implementation-level novelty of every proposed genetic operator or variant.
A candidate solution represents task allocation and per-agent task order using vectors. Instead of relying only on random initialization, the proposed initialization heuristic estimates the cost from each agent's current position to task pickup positions and repeatedly selects a low-cost agent-task pair. The single-objective methods listed in the excerpt are GA-TA, GA-E, Elitist, and Steady State, while the multiobjective methods are NSGA-M, NSGA-ST, and NSGA-O, described as being based on NSGA-II. Tournament selection is used for genetic selection, and the NSGA-II procedure uses nondominated sorting and crowding distance to preserve solutions across objective trade-offs. After allocation, PP, CBS, or PP-E plans the routes needed to execute the resulting task sequences.
The experiments use instances available in the literature and cover two environments: a small environment of size 21 by 35 and a large environment of size 81 by 81. The study varies factors including the number of agents, the number of tasks, environment size, and task arrival rate. Comparisons include Central and TP, which were used in earlier work, as well as combinations involving PP, PP-E, CBS, and the genetic algorithms. Makespan and service time are the main reported objectives, and a solution is considered expired if its computation exceeds five minutes. The supplied excerpt does not provide every parameter, hardware detail, repetition protocol, or complete statistical result.
The reported findings suggest that a decomposed MAPD architecture can be effective when task allocation and path planning are paired appropriately. In the small environment, PP-E combined with GA-TA and the initialization heuristic performed better on every reported instance than the corresponding PP combination, with a stated average improvement of 0.41%. PP-E and PP also outperformed TP, with reported average gains of 5.88% and 5.50%, respectively. CBS produced good solutions but required more processing time, while GA-TA performed better than GA-E among the genetic algorithms mentioned. Future work proposed in the excerpt includes more realistic environments, additional population-initialization heuristics, and experiments on whether free agents should be allowed to exchange their assigned tasks.
Distribution centers are increasingly automated with autonomous mobile robots that transport products. Growth in online purchasing is given as one motivation for studying more efficient warehouse coordination. MAPD models a stream of pickup-and-delivery tasks handled by multiple cooperating agents, while MAPF provides the related framework for finding non-colliding paths on a known map.
Every task requires an agent to visit a pickup position before its delivery position. Poor allocation can increase total completion time or service time, while poor routing can produce conflicts or make an instance unsolvable. The supplied text describes tasks arriving over time and states that the problem ends when no task remains in the system.
Makespan measures the overall time until the relevant tasks are completed, while service time is treated as another task-performance objective. PP plans agents sequentially according to a priority order, whereas CBS searches over conflict resolutions by adding constraints. The text characterizes CBS as having exponential computational complexity with respect to the number of conflicts. PP-E extends the prioritized approach by permitting an agent to move to another free position after reaching its goal in order to avoid future collisions.
The small-environment study varies the path-planning method and genetic algorithm and compares them with Central and TP. The large-environment comparison includes GA-TA, Elitist, Steady State, NSGA-M, NSGA-ST, and NSGA-O. The dissertation also studies objective correlation using randomly generated individuals and independent runs. The excerpt does not establish the full parameter settings or the complete configuration of every experiment.
GA-TA is reported to obtain better results than GA-E. PP-E and PP both outperform TP in the reported comparisons, with average improvements of 5.88% and 5.50%, respectively. When the two approaches are combined with GA-TA and the initialization heuristic, the PP-E combination has a reported average improvement of 0.41% over the PP combination. The excerpt summarizes overall superiority but does not provide all per-instance values or a complete ranking of the multiobjective methods.
The dissertation presents the combination of genetic-algorithm task allocation with established MAPF planning as an effective approach to MAPD. Within the supplied comparisons, GA-TA, PP-E, and the initialization heuristic form a particularly strong combination. The NSGA-II-based formulation adds a way to consider makespan and service time simultaneously rather than optimizing only one time objective.
The supplied evidence does not include complete result tables, confidence intervals, or all genetic-algorithm parameters needed for exact reproduction. Consequently, detailed differences outside the stated averages, and the precise failure conditions of each method, cannot be established from the excerpt. The practical impact of decomposing allocation and routing, the behavior with robot geometry or dynamic obstacles, and the generalization beyond the two tested environments are also not determined by the supplied material.
In MAPD, optimizing allocation and collision-free movement separately can produce locally attractive decisions that are poor for overall throughput. This work is useful because it compares a practical decomposition in which genetic algorithms search task assignments and PP, PP-E, or CBS executes the corresponding movement plans. Considering makespan and service time together is also relevant when warehouse operators must balance system-wide completion with the time spent serving individual tasks.
The paper is suitable for researchers studying MAPD and MAPF, genetic-algorithm task allocation, prioritized planning, CBS, and warehouse-robot coordination. Readers seeking a full reproducibility recipe, a complete theoretical analysis, or direct evidence from physical robots should consult the complete dissertation and its experimental artifacts, because those facts are not established by the supplied excerpt alone.