A Strong Combinatorial Relaxation for the Problem of Min-Time Coverage in Constricted Environments

• 成果类型: Article
• 署名作者: Kim, Young-In; Reveliotis, Spyros
• 署名单位: University System of Georgia; Georgia Institute of Technology
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2023.3298880
• 发表日期: 2024
• 页码: 2963-2978
• 关键词: Combinatorial relaxations of mixed integer programs (MIPs); combinatorial scheduling; coverage problems; multirobot coordination; networked mobile robotic systems

摘要

In a recent work, we introduced a new set of problems in the area of networked multiple mobile robotic systems that concern the time-optimal execution of certain coverage tasks taking place in constricted environments. That work provided the detailed problem definitions, positioned these problems in the context of the corresponding literature, formulated them as mixed integer programs (MIPs), and established their NP-hardness. This article introduces a strong combinatorial relaxation for these problems, and further establishes that the feasible solutions of these relaxations can be converted to feasible solutions for the original MIPs with equal or better objective values than the objective values of the converted solutions. The new results also enable the development of more efficient solution methods and heuristic approaches for the considered problems; this potential is addressed in the last part of this article.