Using Tabu Search to Avoid Concave Obstacles for Source Location

Recently, using a particle swarm optimizer (PSO) to guide robots in a source location problem has attracted widespread interest. While being navigated by PSO, robots are easily trapped into U-shape-like concave obstacles such that they move back and forth cyclically and fail to locate a correct source. Existing obstacle avoidance strategies perform well when robots have information about all obstacles. Yet in many real scenes, robots have no prior information. This work proposes a novel PSO based on Tabu Search (PSO-TS) for robots to locate multiple sources. Instead of traditionally setting obstacles as tabu objects, PSO-TS innovatively sets trapping areas as tabu objects such that robots do not need prior knowledge or expensive hardware and much time to obtain obstacle information. The weighted average velocity of a robot is employed to determine if it is stuck inside an obstacle-induced area. If so, a rectangular tabu area is set to push robots out of the area and prevents robots from searching the same area again. The proposed method can be embedded into various source location algorithms to improve their performance. Its obstacle avoidance capability is proved. Finally, experimental results show the algorithmic compatibility, environmental adaptability and obstacle avoidance performance of the proposed method.

I. Introduction

The source location problem has attracted much concern for its various potential applications. In general, the problem requires intelligent agents such as robots and drones to search for sources in unknown environments with certain constraints [1]. In a source location problem, agents are tasked with finding the location that minimizes or maximizes the scalar field. The field can represent environmental characteristics, such as chemical concentrations, light intensities, or heat. This problem exists in various scenarios, such as environment monitoring, search and rescue operations in a dangerous building, chemical spill investigation and automatic navigation [2], [3], [4], [5], [6], [7]. This work focuses on the following situation: robots are able to obtain the signal strength by their on-board sensor and thus locate signal sources. Signal strength reaches the maximum value where a source is located. Since some tasks might arise in a burning building or cave, source location methods are worth considering especially in dangerous environments where humans may not be safe and general methods like GPS cannot work or incur high cost.