Because this thesis draws from the fields of robotics and qualitative reasoning, it starts with two survey chapters. Chapter 2 presents an overview of research in high level reasoning for robots, and discusses the spatial representations which have been used in several projects. Chapter 3 surveys the brief history of research in qualitative reasoning, covering both representation and reasoning methods, together with problem domains. This chapter includes a critique of qualitative reasoning research with respect to spatial reasoning performance.
Chapter 4 discusses two original qualitative shape and space representation methods, including the ``Extended Polygon Boundary/Partial Distance Ordering'' representation (EPB/PDO). Each method has been developed using a conventional solid modelling paradigm as a starting point. The methods are discussed in terms of the requirements of simple spatial operations. Chapter 5 presents algorithms which use these representations to perform the tasks described above, with some discussion of the implementation that has been carried out. Finally, chapter 6 discusses the utility of the EPB/PDO representation when applied to qualitative reasoning and high level robot reasoning problems. Topics for further investigation in both qualitative reasoning and robot planning are described.
Appendix A gives a full description, in the LISP language, of a scene used for testing the mover's problem system. This example gives some idea of the implementation issues that arise in providing computerised qualitative reasoning, and can be used as a reference for those with further interest in the details of the representation developed in this project.