On Maximising the Total Information Gain in a Vehicle Routing Problem

Abstract

Information gain-based approach is frequently used for exploration in human-machine systems where multiple robots aid a remotely located operator in classification. The amount of information and the marginal increment in information gain depends on the time spent (dwell time) by a robot at the POI. If there are multiple POIs to be monitored, not all of them may be simultaneously monitored. In such a case, the information gain must be discounted by the duration between successive revisits to the same POI. Based on the discounted information gain, a robot can adaptively choose the dwell time for each POI to aid the operator in better classification. This thesis develops a mathematical formulation for maximizing the total discounted information gain when monitoring multiple POIs using a human-machine system. In this framework, an interface typically takes multiple POIs as input from the human operator (who often serves as a classifier-in-the-loop) and computes the order in which they should be visited, and the dwell time of robots sent for monitoring at each POI. The underlying technical problem consists of determining the optimal assignment of POIs to visit for each robot, the sequence of POIs to visit by each robot, and the dwell time at each robot. For the single robot case, the problem simplifies to the determination of last two sets of variables. In this thesis, the log-concavity of total discounted information gain is exploited to show that the optimal routing for the single robot reduces to the determination of optimal tour (using TSP solution), and optimal dwell time through a gradient ascent or equivalent approaches. In the multiple robot case, this thesis presents a partitioning heuristic for POIs based on k-means clustering; once the clusters are determined, a robot is assigned to a cluster to which it belongs, and the resulting problem reduces to the single robot case. Numerical simulations presented corroborate the algorithms developed in this thesis.