Project
Robot Rendezvous
Multi-Place Robot Rendezvous Problem with Campaign Time and Energy Consumption Restrictions
Overview
A tanker robot keeps a team of mobile worker robots running by meeting each of them in turn and recharging its battery. Every meeting can happen at a different place, and both the place and the speed of every robot on every leg are decisions: a robot that moves faster or slower than its energy-optimal speed pays for it in energy. We study two versions of the problem over one set of constraints, minimising the total energy consumed under a limit on the campaign time, and minimising the campaign time itself.
For a fixed meeting order the problem is a second-order cone program: the Euclidean distances are cones as they stand, and each energy constraint becomes a rotated cone once the quadratic-over-linear term is given its own variable. The meeting order is searched with 2-opt and 3-opt edge exchange heuristics adapted from the travelling salesman problem, each candidate order costing one cone program, and with speed-up techniques — fixed-radius search, candidate lists and don't-look bits — that decide which candidates are worth solving at all. The work builds on Nazlı Dolu Hastürk's MSc thesis at Middle East Technical University.
Search Replay
An interactive replay of the meeting-order search. The search view steps through every move the heuristic accepts: the tanker's tour through the rendezvous places the cone program chose, the best candidates it rejected, the objective of every candidate it solved, and, for the speed-up algorithm, the fixed-radius balls and the robots whose don't-look bits are on. The schedule view plays the solution of any step in time, with robots driving to their rendezvous places, the tanker recharging them one by one, and every battery draining and filling.
The runs are on instances generated as in the thesis, with the thesis's energy parameters; they illustrate the method, and the numbers are not the paper's results.
Open Search Replay