A Multirobot Person Search System for Finding Multiple Dynamic Users in Human-Centered Environments

• Published in: IEEE transactions on cybernetics 2023-01, Vol.53 (1), p.628-640
• Main Authors: Mohamed, Sharaf C., Fung, Angus, Nejat, Goldie
• Format: Article
• Language: English
• Subjects: Activities of Daily Living; Algorithms; Buildings; Clustering; Coordination; Environment models; Humans; Min-max multitraveling salesperson problem; Multi-robot systems; multiperiod multiknapsack problem; multiple dynamic people; Multiple robots; multirobot coordination; Optimization; Planning; Probability density functions; Robot kinematics; Robotics; Robotics - methods; Robots; Search and rescue missions; Search problems; search within a deadline; Shortest-path problems; Task analysis; Topology
• ISSN: 2168-2267; 2168-2275
• DOI: 10.1109/TCYB.2022.3166481

Multirobot coordination for finding multiple users in an environment can be used in numerous robotic applications, including search and rescue, surveillance/monitoring, and activities of daily living assistance. Existing approaches have limited coordination between robots when generating team plans or do not consider user location probability within these plans. This results in long searches and robots potentially revisiting the same locations in succession. In this article, we present a novel multirobot person search system to generate search plans for multirobot teams to find multiple dynamic users before a deadline. Our approach is unique in that it simultaneously considers the search actions of all robots and user location probabilities when generating team plans, where user location probabilities are represented as conditional spatial-temporal probability density functions. We model this multirobot person search problem as a two-stage optimization problem to maximize the expected number of users found before the deadline. Stage 1 solves the action selection problem to determine a set of team actions, and the second stage solves the action allocation problem to distribute these actions amongst the robots. Namely, in stage 1, a novel conditional multiperiod multiknapsack problem is modeled as a min-flow graph solved sequentially by the Bellman-Ford shortest path algorithm. Stage 2 is a variant of the min-max multitraveling salesperson problem which models the environment topology as a search region network and search times selected by the previous stage. This stage is solved by a novel fuzzy clustering method. Numerous experiments comparing our proposed method to other existing approaches with varying environment sizes, search durations, and the number of users showed that our approach was able to find more target users before a defined deadline.