A Robot's Response Acceleration Using the Metric Dimension Problem

Consider a robot that is navigating in a space modeled by a graph, and that wants to know its current location. It can send a signal to determine how far it is from each landmark among a set of fixed landmarks. We study the problem of computing the minimum required number of landmarks, and where they should be placed so that the robot can always determine its location. Since the problem is an NP-complete problem, the robot's responses to the actions are slow. To accelerate this response, we can use the parallel version of this problem. In this work, we introduce a new parallel implementation for determining the metric dimension of a given graph. We run the proposed algorithm on a symmetric multi-processing (SMP) cluster using C programming language and the Message Passing Interface (MPI) library. Finally, we run our implementation on four categories of graphs (the tracks in which the robot moves): a cycle graph Cn, a path graph Pn, a triangular snake graph and a ladder graph Ln. Preliminary computational results indicate that the metric dimension problem is an NP-complete problem and prove the ability of the proposed algorithm to achieve a speedup of 6 for 8 processors.