Three robot Search (Two A1s + HSR)

This paper proposes KC-TSS: K-Clustered-Traveling Salesman Based Search, an online path planning algorithm for heterogeneous robot teams performing target search in human environments. We separate the sample path generation problem into a Heterogeneous Clustering and a Traveling Salesman Problems. This allows us to provide quality candidate paths to the Information-Theoretic utility function for each agent. First, we generate waypoint candidates from map knowledge and a target prediction model. All of these candidates are clustered according to the number of agents and their ability to cover space, or coverage competency. Each agent solves a TSP instance over their assigned region and then trajectories are selected using the utility function based on this solution. We perform numerical simulations and validate the framework in a Gazebo-ROS simulation of a real-world apartment setting. The agents leverage an efficient communication structure where only critical information like current location and next waypoints are shared. We compare our proposed method against a state-of-the-art algorithm and show that ours is able to outperform it in mission time. Finally, our method provides resilience in the event of single or multi teammate failure by recomputing the global team plans.