The paper introduces a new, intrinsically discrete, path planning and collision-avoidance problem, with multiple robots and multiple goals. The issue arises in the operation of the novel Swing and Dock (SaD) locomotion for a material handling system. Its agents traverse a base grid by sequences of rotations (swings) around fixed pins. Each agent must visit an array of goal positions in minimal time while avoiding collisions. The corresponding off-line path-planning problem is NP-hard. We model the system by an extended temporal graph and introduce two integer linear programming (ILP) formulations for the minimization of the makespan, with decision variables on the nodes and the edges, respectively. Both optimizations are constrained and favor idling over detours to reduce mechanical wear. The ILP formulations, tailored to the SaD system, are general enough to be applicable for many other single- and multi-agent problems over discretized networks. We have implemented the ILPs with a gurobi solver. Computational results demonstrate and compare the effectiveness of the two formulations.
展开▼
机译：本文介绍了一个新的，本质上离散的路径规划和避免碰撞问题，其中包含多个机器人和多个目标。问题出现在用于物料搬运系统的新型Swing and Dock（SaD）机车的操作中。它的代理通过围绕固定销的旋转（摆动）序列遍历基本网格。每个特工必须在最短的时间内访问一系列目标位置，同时避免碰撞。相应的离线路径规划问题是NP难题。我们通过扩展的时间图对系统进行建模，并引入了两个整数线性规划（ILP）公式以最小化制造期，并分别在节点和边缘上具有决策变量。两种优化都受到限制，并且优先选择空转而不是绕道行驶，以减少机械磨损。针对SaD系统量身定制的ILP公式足够通用，可适用于离散网络上的许多其他单代理和多代理问题。我们已经使用gurobi求解器实现了ILP。计算结果证明并比较了两种配方的有效性。
展开▼
