一种基于时间窗的多机器人路径规划方法

摘要

本发明涉及一种基于时间窗的多机器人路径规划方法，该方法通过已有机器人占用节点的点时间窗和边时间窗，规划新机器人的可行路径，并且在机器人时间窗被打乱时，重新动态规划各个机器人的路径，从而可以避免系统内多机器人的冲突。本发明的多机器人路径规划方法不需要多次迭代，只是在有限的路径集上计算可能性，相对计算量比较小，更适合真实的调度场景应用。

主权项

一种基于时间窗的多机器人路径规划方法，其特征在于，包括如下步骤：1)在多机器人的系统地图中设定节点和短路径，并保存；2)初始化，清除节点和路径的时间窗，清除所有机器人的已规划标记、阻塞标记和循环标记；3)获取各个机器人的速度、位置和状态信息，所述状态包括待规划状态和无需规划状态；使用预定路径搜索算法在预设条件下为各个机器人搜索若干路径，搜索到的路径作为相应机器人的可选路径；4)清除所有机器人的时间窗、已规划标记和循环标记；5)根据所有具有无需规划状态的机器人和具有阻塞标记的机器人的位置和状态更新时间窗；6)选择一个无阻塞标记且无已规划标记的待规划状态的机器人，计算该机器人的每一条可选路径的空闲时间窗，包括该可选路径上各个节点、短路径的空闲时间窗；7)判断步骤6所选择的机器人是否具有可选路径能在对应的空闲时间窗内完成任务。如果有，则选择其中耗时最短的可选路径作为该机器人的行进路径，并对该机器人打上已规划标记，同时更新所有的点时间窗和边时间窗，如果没有，则放宽预设条件，使用所述预定路径搜索算法为该机器人搜索其他路径，如果没能搜索到新的可选路径，则对该机器人打上阻塞标记和循环标记，如果搜索到新的可选路径，则将新路径加入该机器人的可选路径并返回步骤6；8)判断所有无阻塞标记的待规划状态的机器人中，是否还有未被打上已规划标记的机器人，如果有则返回步骤6，如果没有则继续执行以下步骤；9)判断是否还有打上循环标记的机器人，如果有则返回步骤4，如果没有则继续执行以下步骤；10)检测目前系统中是否存在机器人死锁，如果有，则报警。