提出高效机器人调度算法，在路径图上实现近似最优且无碰撞的快速调度。
Fast and Near-Optimal Collision-Free Robot Scheduling On Paths
- 基于动态规划设计新算法PA，适用于路径图上的机器人任务调度。
- PA求解速度比最优整数规划快多个数量级，且多数情况返回最优解。
- 适合需要快速生成高质量调度方案的实验室自动化场景。
本文研究实验室环境中机器人在图结构上的任务调度问题，目标是避免碰撞。我们分析了arXiv:2402.12019中提出的动态规划算法（PA），并引入三种对比基线：可保证最优解的整数规划（IP）、贪心算法（GA）和简单随机算法（RA）。实验表明，对于路径图，PA、GA与RA的求解速度均比IP快多个数量级，且PA在绝大多数情况下获得最优解。在非最优算法对比中，PA产生的平均调度时长不足GA与RA的一半，该优势在不同路径长度、任务持续时间、分布、任务与机器人数量及比例下均保持一致。本工作提出了三种用于线图调度的算法，包括一种新颖的整数规划公式以获取最优解，并证明了PA在接近最优的同时保持良好运行效率。代码已公开于https://github.com/sea26-robots/code。
原文摘要 · Abstract (English)
In this paper, we address the problem of scheduling a set of robots to complete tasks in a laboratory environment, modelled as a graph, while avoiding collisions. We analyze the dynamic programming algorithm (PA) introduced in arXiv:2402.12019 and present three baselines for comparison: an integer programming approach (IP) that always yields an optimal solution, a greedy algorithm (GA), and a simple randomized algorithm (RA). We show that for a path graph, PA, GA, and RA find solutions several orders of magnitude faster than IP (the optimal baseline), with PA returning optimal results in the vast majority of cases. Our scaled experiments comparing non-optimal algorithms show that the average schedule timespan produced by PA is less than half that of RA and GA. This outperformance is consistent across varying path lengths, task durations and distributions, number and allocations of tasks and robots, and task-to-robot ratios. This work serves two purposes. First, we present three algorithms for scheduling on line graphs, including a novel integer programming formulation for finding optimal solutions. Second, we demonstrate that PA produces near-optimal schedules that outperform all non-optimal baselines while maintaining a comparable runtime. Code is available at https://github.com/sea26-robots/code.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。