A linear relaxation solution of the Tactical Movement Problem

The Tactical Movement Problem seeks to determine the minimum cost mission for a robotic agent tasked to complete an assignment that involves both moving through its environment and manipulating that environment. The problem arises in several contexts including open-pit mining automation when a robotic excavator is tasked to remove a designated area of material. The work involves the excavator progressively digging earth, which is usually loaded to trucks. After each load cycle, a decision about from where to take the next dig must be made. Periodically this involves moving the excavator to a new location. The objective is to complete the task in minimum time or at a minimum energy cost or some similarly motivated cost function. The problem becomes one of determining the optimal path that the excavator should take and the dig operations that should be completed at each point along the path. In this paper the problem is posed as a linear relaxation that is solved successively to near optimality. Simulated results show that cost effective paths can be generated however there is still significant computation burden due to the high complexity of the problem. This result allows the solution of much larger task planning problems than were previously possible, thus moving towards the goal of cost effective automated excavation.