期刊
IEEE TRANSACTIONS ON CYBERNETICS
卷 51, 期 12, 页码 6274-6283出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TCYB.2020.2974832
关键词
Task analysis; Planning; Heuristic algorithms; Genetic algorithms; Optimization; Sorting; Cybernetics; Heuristic algorithms; lower bound; precedence constraints; task planning; topological sorting
类别
资金
- National Natural Science Foundation of China [61603094, 61633002]
This article investigates a task planning problem, constructs a lower bound on the optimal solution based on graph theory, proposes a new topological sorting strategy, and designs several heuristic algorithms to solve the problem, which outperform popular genetic algorithms in numerical experiments.
This article investigates the task planning problem where one vehicle needs to visit a set of target locations while respecting the precedence constraints that specify the sequence orders to visit the targets. The objective is to minimize the vehicle's total travel distance to visit all the targets while satisfying all the precedence constraints. We show that the optimization problem is NP-hard, and consequently, to measure the proximity of a suboptimal solution from the optimal, a lower bound on the optimal solution is constructed based on the graph theory. Then, inspired by the existing topological sorting techniques, a new topological sorting strategy is proposed; in addition, facilitated by the sorting, we propose several heuristic algorithms to solve the task planning problem. The numerical experiments show that the designed algorithms can quickly lead to satisfying solutions and have better performance in comparison with popular genetic algorithms.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据