Contatto di riferimento: Prof. Paolo Toth
Abstract
Single-robot search, similarly to exploration, can be understood as a process of autonomous navigation of a mobile robot in an unknown environment in order to find an object of interest. The search algorithm can be formulated as the iterative procedure consisting of model updating with actual sensory data, the selection of a new goal for each robot based on the current knowledge of the environment, and the subsequent navigation to this goal. A natural condition is to perform the search with an expected minimal usage of resources, e.g., trajectory length, time of search, or energy consumption. At first sight the problem seems to be similar to exploration, which has been thoroughly studied by the robotic community. Indeed, a general framework for search can be derived from frontier-based exploration, but the strategies for the selection of a next goal to which navigate a robot cannot be simply reused.
In this talk we introduce the single-robot search problem in an unknown environment. We will review how the solution of a Traveling Salesman Problem (TSP) can be used to select the next goal candidate in the single-robot exploration context every time new data from the sensor is obtained, usually within one second of computing time. For the search problem, the selection of the next goal can be formulated as a generalization of Traveling Deliveryman Problem (TDP) where each vertex has also an associated weight (i.e., probability that the object will be discovered when visiting that vertex). However, the computing times of the best exact algorithms for the TDP are still prohibitive within this context, even for moderate size instances. We will therefore present some heuristic approaches we are currently investigating to solve this problem within very short computing times and discuss some preliminary computational results on a simulation environment.