Given a mapped environment, we formulate the problem of visually tracking and following an evader using a probabilistic framework. In this work, we consider a non-holonomic robot with a limited visibility depth sensor in an indoor environment with obstacles. The mobile robot that follows the target is considered a pursuer and the agent being followed is considered an evader. We propose a probabilistic framework for both the pursuer and evader to achieve their conflicting goals. We introduce a smart evader that has information about the location of the pursuer. The goal of this variant of the evader is to avoid being tracked by the pursuer by using the visibility region information obtained from the pursuer, to further challenge the proposed smart pursuer. To validate the efficiency of the framework, we conduct several experiments in simulation by using Gazebo and evaluate the success rate of tracking an evader in various environments with different pursuer to evader speed ratios. Through our experiments we validate our hypothesis that a smart pursuer tracks an evader more effectively than a pursuer that just navigates in the environment randomly. We also validate that an evader that is aware of the actions of the pursuer is more successful at avoiding getting tracked by a smart pursuer than a random evader. Finally, we empirically show that while a smart pursuer does increase it's average success rate of tracking compared to a random pursuer, there is an increased variance in its success rate distribution when the evader becomes aware of its actions.
Megiddo @cite_12 proved that the complexity of searching a graph, which is equivalent to the search number, is NP-hard. In both these cases, visibility is not considered. The evader is found or captured if and only if both pursuer and evader are on the same vertices of the graph. The cop number is defined as a theoretical limit on the number of pursuers that can be used on a particular graph to successfully capture an evader. The cop number varies for different graphs based on the structure (topology) of the graph. Since we use a single pursuer in our work, we need not consider the cop number, instead we focus on finding a goal location for the pursuer that will maximize it's tracking rate.
@cite_12
2154788235
T. Parsons originally proposed and studied the following pursuit-evasion problem on graphs: Members of a team of searchers traverse the edges of a graph G in pursuit of a fugitive, who moves along the edges of the graph with complete knowledge of the locations of the pursuers. What is the smallest number s ( G ) of searchers that will suffice for guaranteeing capture of the fugitive? It is shown that determining whether s ( G ) ≤ K , for a given integer K , is NP-complete for general graphs but can be solved in linear time for trees. We also provide a structural characterization of those graphs G with s ( G ) ≤ K for K = 1, 2, 3.