In surface mining, large excavators are used to dig and load material to trucks for transport to processing plants or waste material areas. The operators of these machines typically work twelve hours shifts; the work is repetitive, but requires skill to execute competently. There are good reasons for automating these machines so that they can work without an operator. Automation is expected to deliver higher productivity and lower duty through consistent operation.
An automated mining excavator will require the capability to plan its work, or missions, replacing the functions currently performed by the operator in deciding where to dig from next and when are where to move to in excavating a block of material. In its pure form, this is a combinatorial optimization problem. An uncountable set of sequences of digs and machine movements could potentially be enacted to excavate a block of material. It is desired to choose the best such sequence, where best is, for example, measured by, the shortest time taken to complete the excavation sequence.
While for any given mission the problem could be solved off-line, such a solution would have little value. The problem is characterised by the uncertainty associated with how the terrain is changed by the action of digging. Each dig involves a complex flow of material into the bucket and disruption of the surrounding material that cannot be a priori predicted. For this reason, the problem must be resolved after each dig, taking into account the current terrain geometry and finding the best sequence of actions to complete the remainder of the task.
This thesis addresses the problem of planning and executing excavation sequences to minimize excavation cost. This problem is termed the Tactical Movement Problem. The aims of the the thesis are to: (i) examine the key complexities of planning for the Tactical Movement Problem and how these can be represented; (ii) provide a mathematical definition of the Tactical Movement Problem capturing salient characteristics; and (iii) develop a planning algorithm capable of solving the Tactical Movement Problem, thus determining the sequence of excavator actions required to complete a excavation mission. The ability to solve the problem within the time normally available between digs is of crucial importance.
The Tactical Movement Problem is defined in an optimisation framework and the complexity of the optimisation is compared to known problems in literature. A simplified representation of the excavation planning problem is shown to be the coupled solution of two known NP hard problems, the Travelling Salesman Problem and the Set Cover Problem. A linear relaxation solution is developed for this coupled problem and compared to state-of-the-art mixed integer linear programming solution methods. Improvements in computation time for the linear relaxation problem of two orders of magnitude are achieved while maintaining a near optimal solution. The thesis further develops a novel multiple-level-of-detail approach to solving the excavation task planning problem that uses a grid based representation of the environment. Wavelet transformation is used to generate coarse approximations of the terrain to be excavated, which are in turn used to produce task plans rapidly. The coarse plans are used as a guide for planning at successively finer levels of detail thus maintaining the near globally optimal solution while reducing computation time.
This algorithm is implemented on a scale robotic excavator and the approach is evaluated by comparison with a greedy algorithm. This excavator is able to simulate a mining excavator at a scale of 25:1 and can complete high level tasks assigned to it without human intervention. The multiple level of detail algorithm is shown to be robust to working in a scaled mining environment. This verification of the algorithm shows that the multiple-level-of-detail algorithm meets the requirements for a fully autonomous excavation task planner.
Original contributions are made toward automated excavation through the design, implementation and verification of an optimisation based tactical level planner. The general nature of the algorithm makes it suitable for implementation in other task planning problems in which a surface environment must be manipulated by a mobile robot.