Journal
IEEE TRANSACTIONS ON CYBERNETICS
Volume 51, Issue 12, Pages 6274-6283Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TCYB.2020.2974832
Keywords
Task analysis; Planning; Heuristic algorithms; Genetic algorithms; Optimization; Sorting; Cybernetics; Heuristic algorithms; lower bound; precedence constraints; task planning; topological sorting
Categories
Funding
- National Natural Science Foundation of China [61603094, 61633002]
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available