Selected Publications

Doctoral Thesis, Department of Computer Science, University of British Columbia

A Constraint-Based Approach for Computing Fault-Tolerant Robot Programs


We develop a new framework, based on the Least Constraint, for programming robots to perform a task using a fault tolerant trajectory. We take a specification of the task, expressed as a set of constraints on the robot's configuration over time, and produce a fault tolerant trajectory. The methodology encourages fault tolerant behavior at two levels: first at the task-design phase by encouraging the designer to omit extraneous constraints which reduce the potential for fault tolerant operation, and secondly, at the trajectory generation phase by avoiding critical configurations. The critical configurations are identified via a measure of fault tolerance which is global in nature. The dual optimization of fault tolerance at both the high-level design phase as well as the low-level recovery motion generation phase allows more of the inherent fault tolerance of the robot to be exploited. We believe that combining these two processes into a single formalism is unique and beneficial. The methodology is unique in its ability to deal with robots which are not kinematically redundant with respect to arbitrary task, but which are sufficiently redundant with respect to the particular task constraints to allow the task to be described as a set of "loose" constraints over time. The constraint-based approach allows us to model faults as additional constraints to the specification, thereby allowing an efficient means of computing the effect a fault will have on the ability to complete the task, using the reduced configuration space of the robot. Faults not previously considered, such as the inclusion of additional obstacles, as well as dynamic information arising from sensors, can also be included using this formalism. An efficient algorithm for constructing a recovery motion for a fault has been developed. A specific example of a seldom considered fault, the collision of the robot with an unknown obstacle, is presented. We show that in addition to detecting the event, we are also able to recover the collision geometry. This information can then be used in a more intelligent recovery motion selection. We have developed a new global fault tolerance measure called longevity. The fault tolerance measure examines a set of faults which may occur at a given configuration, and based on the optimal recovery motions for the given fault, ranks the configuration in its ability to satisfy the future task requirements. Using this fault tolerance measure, a trajectory which maximizes the worst-case failure mode of the robot is computed. A number of experiments show the applicability of the method to a number of domains. We analyze the resulting trajectories with respect to their ability to sustain a fault, and we compare them to more traditional methods for accomplishing the same task. We demonstrate that trajectories obtained using the least constraint specification and the fault tolerance measure are able to achieve a much larger degree of fault tolerance than naive methods for the same task. The fault tolerant trajectories make optimal use of the 1-fault tolerant configuration space, and maximize the worst-case utility of the trajectory given a fault.

Full Text

Masters Thesis, Department of Computer Science, University of British Columbia

A Neural Network Implementation for Integrating Discontinuity and Displacement Information


An artificial neural network is presented which performs the task of integrating discontinuity and displacement information to produce an estimate of displacement which is robust in portions of the image containing discontinuous motion. The behavior of the algorithm is learned from a series of randomly generated examples, and demonstrates that the necessary constraints required to perform fundamental visual computation can be extracted directly from a series of random images. By phrasing the problem as a machine-learning problem we are able to give explicitly the optimality criteria (given by the learning rule), without making explicit assumptions on the image features necessary to perform the computation. The motion primitives consist of the sum-of-squared-differences (SSD) values over a set of oriented rectangular support regions. A set of related measures, called shear values, are used to detect the position and orientation of discontinuities in the displacement field. By using a set of support regions which vary in shape and size, the algorithm is able to exploit the discontinuity information and choose the support region which best captures the underlying motion of the region. The resulting algorithm is compared to the traditional SSD algorithm with a single square support region, using both natural and synthetic images. Analysis of the algorithm indicates the neural network is able to reduce the distortion effects occurring near discontinuities and produces object boundaries which are significantly better representations of the object's true structure. The computed displacements show the neural network is able to interpolate over the SSD surface to produce displacements which are within sub-pixel accuracy. Additional confidence measures are given for the neural network and are compared to the traditional SSD algorithm.

Full Text

“Video Surveillance at Night”

Stevens, M. R., Pollak, J., Ralph, S., and Snorrason, M.,
Proceedings SPIE Defense & Security, vol 5810. Orlando, FL (April), 2005. Full Text (pdf)

“Detection and Localization of Un-modeled Manipulator Collisions,”

Scott K. Ralph and Dinesh K. Pai,
IEEE International Conference on Intelligent Robots and Systems, 1995, Vol. 2, p 504-509. Full Text (pdf)

“Fault Tolerant Locomotion for Walking Robots,”

Scott K. Ralph and Dinesh K. Pai, IEEE International Symposium on Computational Intelligence in Robotics and Automation, 1997, pp. 130-137. Full Text (pdf)

“Assessing the Performance of an Automated Video Ground Truthing Application”,

Scott K. Ralph, J. Irvine, M. Stevens, M. Snorrason, and D. Gwilt, Proceedings of Applied Imagery Pattern Recognition, Washington DC (October, 2004). Full Text (pdf)

“An Image Metric-Based ATR Performance Prediction Testbed”

Ralph, S., Irvine, J., Snorasson, M., Stevens, M. and Vanstone, S., Proceedings of the Applied Imagery and Pattern Recognition Workshop, Washington, DC, (October, 2005) Full Text (pdf)

“Computing Fault Tolerant Motions for a Robot Manipulator,”

Scott K. Ralph and Dinesh K. Pai, IEEE Conference on Robotics and Automation, 1999. Full Text (pdf)

“Platonic Beasts: Spherically Symmetric Multilimbed Robots,”

Autonomous Robots, 1995, Vol. 2, No. 3, pp 191-201. Full Text (pdf)

“START for Evaluation of Target Detection and Tracking,”

Irvine, J. M., Ralph, S., Stevens, M. R., Marvel, J., Snorrason, M., and Gwilt, D., Proceedings SPIE Defense & Security, Vol. 5807. Orlando, FL (April), 2005. Full Text (pdf)

“Evaluation Testbed for ATD Performance Prediction (ETAPP)”

Scott K. Ralph , Mark R. Stevens, Magnús Snorrason, and John Irvine, “ Proceedings SPIE Defense & Security, Orlando, FL (April, 2006) Full Text (pdf)