Integrating Online Task Assignment and Lifelong Path Finding

This paper addresses the combined problem of online task assignment and lifelong path finding in logistics warehouses. The authors introduce a formal framework and a solution concept that integrates task assignment with continuous path planning. They propose a rule-based lifelong planner designed for a practical robot model and automate search for the task assigner that works with that planner. Simulation results in warehouse scenarios at Meituan report time and economic efficiency gains compared with the currently deployed system and other state-of-the-art algorithms.

What the study examined

The work looks at the combined problem of online task assignment and lifelong path finding, a setting where tasks arrive over time and robots must repeatedly plan paths to complete them. The authors note that prior research tended to treat the two parts separately or assume tasks are known in advance, and argue that integrating them in an online setting is important for improving system throughput.

To address this, the paper introduces a formal framework and a solution concept for the integrated problem. The study focuses on a practical robot model and on solutions that can operate under persistent, ongoing task streams rather than a single offline batch of tasks.

Key findings

The authors design a rule-based lifelong planner that is reported to handle environments with severe local congestion effectively. They then automate the search for a task assigner that is tuned to the behavior of the underlying path planner.

• In simulation experiments using warehouse scenarios at Meituan, the system required 83.77% of the execution time needed by the system currently deployed at Meituan, and it outperformed other state-of-the-art algorithms by 8.09% in time efficiency.
• In terms of economic efficiency, the reported results indicate the same throughput can be achieved with only 60% of the agents currently in use at Meituan.

Why it matters

Integrating task assignment and lifelong path finding addresses the reality that warehouse operations run continuously and must balance which tasks are assigned with how robots move. The formal framework and the combination of a rule-based planner with an automated task-assigner search provide a concrete approach for this integrated setting.

Reported simulation gains in execution time and agent use suggest potential operational efficiencies in warehouse logistics, while the practical robot model and attention to congestion highlight relevance to real-world deployments. Code and demonstrations related to the work are made available by the authors.