Fingerprint-based indoor localization methods are promising due to the high availability of deployed access points and compatibility with commercial-off-the-shelf user devices. However, to train regression models for localization, an extensive site survey is required to collect fingerprint data from the target areas. In this paper, we consider the problem of informative path planning (IPP) to find the optimal walk for site survey subject to a budget constraint. IPP for location fingerprint collection is related to the well-known orienteering problem (OP) but is more challenging due to edge-based non-additive rewards and revisits. Given the NP-hardness of IPP, we propose two heuristic approaches: a Greedy algorithm and a genetic algorithm. We show through experimental data collected from two indoor environments with different characteristics that the two algorithms have low computation complexity, can generally achieve higher utility and lower localization errors compared to the extension of two state-of-the-art approaches to OP.
RO was originally introduced in @cite_9 . The basic idea is to convert OP into two sub-problems: the subset selection problem and the travelling salesman problem (TSP). Specifically, vertices are randomly added and removed from the current vertex set, and path planning is done via a TSP solver among the selected vertex set. Such an approach requires that the graph is fully connected. Additionally, the utility is additively associated with the vertices and costs arise from the edges. Thus, once the set of vertices is determined, the utility is also determined. It suffices to use a TSP solver to find the least cost path to traverse those vertices.
@cite_9
2737130609
Maximizing information gathered within a budget is a relevant problem for information gathering tasks for robots with cost or operating time constraints. This problem is also known as the informative path planning (IPP) problem or correlated orienteering. It can be formalized as that of finding budgeted routes in a graph such that the reward collected by the route is maximized, where the reward at nodes can be dependent. Unfortunately, the problem is NP-Hard and the state of the art methods are too slow to even present an approximate solution online. Here we present Randomized Anytime Orienteering (RAOr) algorithm that provides near optimal solutions while demonstrably converging to an efficient solution in runtimes that allows the solver to be run online. The key idea of our approach is to pose orienteering as a combination of a Constraint Satisfaction Problem and a Traveling Salesman Problem. This formulation allows us to restrict the search space to routes that incur minimum distance to visit a set of selected nodes, and rapidly search this space using random sampling. The paper provides the analysis of asymptotic near-optimality, convergence rates for RAOr algorithms, and present strategies to improve anytime performance of the algorithm. Our experimental results suggest an improvement by an order of magnitude over the state of the art methods in relevant simulation and in real world scenarios.