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.
Subject
human-machine systemInformation gain
dwell time
UAV
VRP
TSP
Automatic Target Recognition
classifier-in-the-loop
Receiver-Operating Curve
confusion matrix
human operator
classification
conditional probability distributions
Unmanned Aerial Vehicles
POI
Vehicle Routing
Kullback-Leibler divergence
Mutual Information
information-theoretic approach
optimization
Problem Based method
K − means clustering
Citation
Kumar, Suveer (2023). On Maximising the Total Information Gain in a Vehicle Routing Problem. Master's thesis, Texas A&M University. Available electronically from https : / /hdl .handle .net /1969 .1 /200130.