A Dijkstra-inspired graph algorithm for fully autonomous tasking in industrial applications
Date
2021-09
Embargo
Advisor
Coadvisor
Journal Title
Journal ISSN
Volume Title
Publisher
Instituto de Engenheiros Elétricos e Eletrônicos
Language
English
Alternative Title
Abstract
An original graph-based model and algorithm for optimal industrial task scheduling are proposed in this article. The innovative algorithm designed, dubbed “Dijkstra optimal tasking” (DOT), is suitable for fully distributed task scheduling of autonomous industrial agents for optimal resource allocation, including energy use. The algorithm was designed starting from graph theory fundamentals, from the ground up, to guarantee a generic nature, making it applicable on a plethora of tasking problems and not case-specific. For any industrial setting in which mobile agents are responsible for accomplishing tasks across a site, the objective is to determine the optimal task schedule for each agent, which maximizes the speed of task achievement while minimizing the movement, thereby minimizing energy consumption cost. The DOT algorithm is presented in detail in this manuscript, starting from the conceptualization to the mathematical formulation based on graph theory, having a thorough computational implementation and a detailed algorithm benchmarking analysis. The choice of Dijkstra, as opposed to other shortest path methods (namely, A * Search and Bellman-Ford) in the proposed graph-based model and algorithm, was investigated and justified. An example of a real-world application based on a refinery site is modeled and simulated and the proposed algorithm's effectiveness and computational efficiency are duly evaluated. A dynamic obstacle course was incorporated to effectively demonstrate the proposed algorithm's applicability to real-world applications.
Keywords
Graph theory, Algorithms, Task scheduling, Energy management, Dijkstra, Industrial applications
Document Type
Journal article
Publisher Version
10.1109/TIA.2021.3091418
Dataset
Citation
Lotfi, M., Osório, G. J., Javadi, M, Ashraf, A., Zahran, M., Samih, G., & Catalão, J. P. S. (221). A Dijkstra-inspired graph algorithm for fully autonomous tasking in industrial applications. IEEE Transactions on Industry Applications, 57(5), 5448-5460. DOI: 10.1109/TIA.2021.3091418. Disponível no Repositório UPT, http://hdl.handle.net/11328/3710
Identifiers
TID
Designation
Access Type
Open Access