Online Multi-Agent Task Assignment and Path Finding With Kinematic Constraint in the Federated Internet of Things

被引:3
作者
Hou, Yunfeng [1 ]
Ma, Zhiyuan [1 ,2 ]
Pan, Zhichun [1 ]
机构
[1] Univ Shanghai Sci & Technol, Inst Machine Intelligence, Shanghai 200093, Peoples R China
[2] Nanjing Univ, State Key Lab Novel Software Technol, Nanjing 210093, Peoples R China
关键词
Task analysis; Robots; Costs; Service robots; Robot sensing systems; Robot kinematics; Planning; Multi-agent; task assignment; path finding; Federated Internet of Things; kinematic constraint; warehouse; RELATIVE OBSERVABILITY; SUPERVISORY CONTROL; DISCRETE;
D O I
10.1109/TCE.2023.3319043
中图分类号
TM [电工技术]; TN [电子技术、通信技术];
学科分类号
0808 ; 0809 ;
摘要
In this paper, we propose a novel algorithm to solve multi-agent task assignment and path finding (MATAPF) problem in the Federated Internet of Things (FIoT). Conventional MATAPF studies mostly take the form of two-phase planning that assigns tasks to the agents, then finds inter-agent collision-free paths to accomplish these tasks. In contrast, we consider the task assignment problem and the path finding problem at the same. The agents can adjust their paths according to the changing task assignment situations such that all the tasks can be finished in the minimum distance cost. This is realized by constructing an automaton model to incorporate the movements of the agents and the execution process of the tasks. An optimal controller is designed to assign each newly issued task to the most appropriate agent and to control all the agents to their target positions safely (without collision and deadlock) and efficiently (in the minimum distance cost) at each time step. Additionally, when we construct the roadmap for multi-agent path finding, we consider the kinematic constraint of each agent. That is, from any position of the roadmap, all its successive positions are physically reachable to all the agents, which can improve the efficiency of the path planning, especially when there exist a large number of agents. As a case study, we then apply this online control scheme to model and control a warehouse automation system, which is a common FIoT application scenario. Simulations in various layouts of the warehouse demonstrate that MATAPF significantly outperforms standard approaches, i.e., solving more problem instances much faster. The effectiveness of the proposed framework has also been tested for a increasing number of agents.
引用
收藏
页码:2586 / 2595
页数:10
相关论文
共 40 条
  • [1] New Algorithms for Verification of Relative Observability and Computation of Supremal Relatively Observable Sublanguage
    Alves, Marcos V. S.
    Carvalho, Lilian K.
    Basilio, Joao C.
    [J]. IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2017, 62 (11) : 5902 - 5908
  • [2] FORMULAS FOR CALCULATING SUPREMAL CONTROLLABLE AND NORMAL SUBLANGUAGES
    BRANDT, RD
    GARG, V
    KUMAR, R
    LIN, F
    MARCUS, SI
    WONHAM, WM
    [J]. SYSTEMS & CONTROL LETTERS, 1990, 15 (02) : 111 - 117
  • [3] Brown K, 2020, IEEE INT CONF ROBOT, P441, DOI [10.1109/icra40945.2020.9197527, 10.1109/ICRA40945.2020.9197527]
  • [4] Relative Observability of Discrete-Event Systems and Its Supremal Sublanguages
    Cai, Kai
    Zhang, Renyuan
    Wonham, W. M.
    [J]. IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 2015, 60 (03) : 659 - 670
  • [5] Mobile Crowdsourced Guiding and Finding With Precise Target Positioning Based on Internet-of-Things Localization
    Chen, Lien-Wu
    Liu, Jun-Xian
    [J]. IEEE TRANSACTIONS ON SYSTEMS MAN CYBERNETICS-SYSTEMS, 2022, 52 (08): : 4849 - 4861
  • [6] Edge-Based Optimal Routing in SDN-Enabled Industrial Internet of Things
    Desai, Prasad Ramesh
    Mini, S.
    Tosh, Deepak K.
    [J]. IEEE INTERNET OF THINGS JOURNAL, 2022, 9 (19): : 18898 - 18907
  • [7] Grenouilleau F., 2019, INT C AUTOMATED PLAN, V29, P181, DOI 10.1609/icaps.v29i1.3474
  • [8] Heymann M., 1994, Discrete Event Dynamic Systems: Theory & Applications, V4, P221, DOI 10.1007/BF01438708
  • [9] Hönig W, 2018, PROCEEDINGS OF THE 17TH INTERNATIONAL CONFERENCE ON AUTONOMOUS AGENTS AND MULTIAGENT SYSTEMS (AAMAS' 18), P757
  • [10] Hou Y., 2023, IEEE Trans. Control Netw. Syst.