Algorithms for Collision Hulls and their Applications to Path Planning

Zane Smith (2008). Algorithms for Collision Hulls and their Applications to Path Planning PhD Thesis, School of Mechanical and Mining Engineering, The University of Queensland.

Attached Files (Some files may be inaccessible until you login with your UQ eSpace credentials)
Name Description MIMEType Size Downloads
s40108452_PhD_finalthesis.pdf Final version of thesis application/pdf 7.01MB 17
Author Zane Smith
Thesis Title Algorithms for Collision Hulls and their Applications to Path Planning
School, Centre or Institute School of Mechanical and Mining Engineering
Institution The University of Queensland
Publication date 2008-10
Thesis type PhD Thesis
Total pages 202
Total colour pages 9
Total black and white pages 193
Subjects 09 Engineering
Abstract/Summary The potential benefits that automation could bring to a wide variety of real-world tasks are numerous and well recognised. There has been significant research undertaken into automation in general, but for real-time automation of complex systems (involving complex geometries and dynamics) the problem is far from a solved one. One of the key tasks in a surface mining operation is that of using shovels or excavators to load material onto haul trucks for transportation. Since it is such a crucial task to a number of production cycles, it is a clear area where the productivity and safety benefits of automation could have a large impact. A number of projects are being undertaken concurrently to move towards first partial, and then full, automation of this mining subsystem. This thesis focusses on the collision avoidance problem, specifically on forming a collision hull that distinguishes between intersecting and non-intersecting configurations of two objects. Techniques from computer graphics are leveraged to develop a data structure that stores and organises relevant information about real-world systems for motion-planning tasks, ensuring that the necessary data is available and in a form suited to the task at hand. The Minkowski Sum operation, which can be used fairly directly to form the collision hull of two convex objects under translation, is extended to develop an operation to form the exact collision hull of two arbitrary objects to determine the applicability of such a scheme to complex systems in real-time. A level of detail solution is then proposed, where the Minkowski Hull of bounding hierarchies allows unnecessary parts of the hull to be calculated only in a coarse manner, thus offsetting a lot of the computational cost for any given test. This approach is investigated for both translational motion and joint-space motion. Collision detection is not collision avoidance, and so the algorithms developed in the thesis are tested in a number of applications, to demonstrate their suitability to the collision avoidance task. The applications (discrete collision prediction, visibility graph path planning, and the formulation of a Model Predictive Controller) are restricted versions of the true problems with some simplifying assumptions, but they show the algorithms to be capable both in their execution speed and the information that they provide.
Keyword Minkowski Sum
collision hull
collision avoidance
path planning
mining automation
Additional Notes 32, 67, 73, 94, 108, 116, 117, 142, 148

Citation counts: Google Scholar Search Google Scholar
Created: Mon, 28 Jun 2010, 08:06:42 EST by Mr Zane Smith on behalf of Library - Information Access Service