Spatial Reasoning for Robots:
A Qualitative Approach

by


Alan Frank Blackwell


A thesis

submitted to the Victoria University of Wellington
in fulfilment of the
requirements for the degree of
Master of Science
in Computer Science.

Victoria University of Wellington

October 1988

Abstract

This thesis presents a new approach to the problem of shape representation for high level robot reasoning tasks. Techniques from the field of qualitative physics are combined with current methods for solid modelling to develop a qualitative representation of two dimensional shape and position. The qualitative spatial representation has been used to solve simple spatial reasoning tasks. The results of this investigation are applicable both to the field of robotics, where they provide a new approach to programming and control, and to the field of qualitative physics, which has been hampered by a lack of general purpose spatial reasoning techniques.

Acknowledgements

Thanks to Peter Andreae, my supervisor, for his fund of ideas and his energetic criticism. Also to PROGENI, for the use of office facilities, and for extended periods of study leave. Thanks for advice, assistance, and friendship to Mark, Karen, Duncan, Bernd, Paul, Craig, Julie, Jonathan, Matthew, Andrew, Mike, David, Evan, Philip, Alvin, Alex, Clifton and Steve. Thanks to my musical friends for a life beyond study, especially Harry and Gillian. Lastly, thanks to Helen. This project would never have commenced, progressed, or been completed without her encouragement and support.