Hexplorer is a six-legged walking robot developed at the University of Waterloo. The robot is controlled by a network of seven digital signal processors, six of which control three motors each, for a total of 18 motors. Brand new custom electronics were designed to house the digital signal processors and associated circuitry. A variable duty factor wave gait, developed by Yoneda et al. was simulated and implemented on the robot. Simulation required an in-depth kinematic analysis that was complicated by the mechanical design of parallel mechanism comprising the legs. These complications were handled in both simulation and implementation. However, due to mechanical issues Hexplorer walked for only one or two steps at a time.

Hexplorer is a six-legged walking robot developed at the University of Waterloo. The robot is controlled by a network of seven digital signal processors, six of which control three motors each, for a total of 18 motors. Brand new custom electronics were designed to house the digital signal processors and associated circuitry. A variable duty factor wave gait, developed by Yoneda et al. was simulated and implemented on the robot. Simulation required an in-depth kinematic analysis that was complicated by the mechanical design of parallel mechanism comprising the legs. These complications were handled in both simulation and implementation. However, due to mechanical issues Hexplorer walked for only one or two steps at a time.

In this work we focus on building local maps to enable wheeled mobile robots to navigate safely and autonomously in urban environments. Urban environments present a variety of hazards that mobile robots have to detect and represent in their maps to navigate safely. Examples of hazards include obstacles such as furniture, drop-offs such as at downward stairs, and inclined surfaces such as wheelchair ramps. We address two shortcomings perceived in the literature on mapping. The first is the extensive use of expensive laser-based sensors for mapping, and the second is the focus on only detecting obstacles when clearly other hazards such as drop-offs need to be detected to ensure safety. Therefore, in this work we develop algorithms for building maps using only relatively inexpensive stereo cameras, that allow safe local navigation by detecting and modeling hazards such as overhangs, drop-offs, and ramps in addition to static obstacles. The hazards are represented using 2D annotated grid maps called local safety maps. Each cell in the map is annotated with one of several labels: Level, Inclined, Non-ground, or, Unknown. Level cells are safe for travel whereas Inclined cells require caution. Non-ground cells are unsafe for travel and represent obstacles, overhangs, or regions lower than safe ground. Level and Inclined cells can be further annotated as being Drop-off Edges. The process of building safety maps consists of three main steps: (i) computing a stereo depth map; (ii) building a 3D model using the stereo depths; and, (iii) analyzing the 3D model for safety to construct the safety map. We make significant contributions to each of the three steps: we develop global stereo methods for computing disparity maps that use edge and color information; we introduce a probabilistic data association method for building 3D models using stereo range points; and we devise a novel method for segmenting and fitting planes to 3D models allowing for a precise safety analysis. In addition, we also develop a stand-alone method for detecting drop-offs in front of the robot that uses motion and occlusion cues and only relies on monocular images. We introduce an evaluation framework for evaluating (and comparing) our algorithms on real world data sets, collected by driving a robot in various environments. Accuracy is measured by comparing the constructed safety maps against ground truth safety maps and computing error rates. The ground truth maps are obtained by manually annotating maps built using laser data. As part of the framework we also estimate latencies introduced by our algorithms and the accuracy of the plane fitting process. We believe this framework can be used for comparing the performance of a variety of vision-based mapping systems and for this purpose we make our datasets, ground truth maps, and evaluation code publicly available. We also implement a real-time version of one of the safety map algorithms on a wheelchair robot and demonstrate it working in various environments. The constructed safety maps allow safe local motion planning and also support the extraction of local topological structures that can be used to build global maps. / text

Randomly scattered sensors may cause sensing holes and redundant sensors. In carrier-based sensor relocation, mobile robots (with limited capacity to carry sensors) pick up additional or redundant sensors and relocate them at sensing holes. In the only known localized algorithm, robots randomly traverse field and act based on identified pair of spare sensor and coverage hole. We propose a Market-based Sensor Relocation (MSR) algorithm, which optimizes sensor deployment location, and introduces bidding and coordinating among neighboring robots. Sensors along the boundary of each hole elect one of them as the representative, which bids to neighboring robots for hole filling service. Robot randomly explores by applying Least Recently Visited policy. It chooses the best bid according to Cost over Progress ratio and fetches a spare sensor nearby to cover the corresponding sensing hole. Robots within communication range share their tasks to search for better possible solutions. Simulation shows that MSR outperforms the existing competing algorithm G-R3S2 significantly on total robot traversed path and energy, and time to cover holes, slightly on number of sensors needed to cover the hole, and the cost of additional messages for bidding and deployment location sharing.

This thesis looks at the problem of optimally placing binary directional proximity markers to assist a robot as it navigates waypoints through an environment. A simple planar fiducial marker is developed to serve as the binary directional proximity marker. A scoring function is proposed for marker placement as well as a method for random generation of hallway maps. Several common metaheuristic algorithms are run to find optimal marker placements with respect to the scoring function for a number of randomly generated hallway maps. From these results, placements are then evaluated by physical experimentation on an iRobot Create equipped with relatively inexpensive webcams. / Graduate

Autonomous robots typically rely on internal representations of the environment, or maps, to plan and execute their tasks. Several types of maps have been proposed in the literature, and there is general consensus that different types have different advantages and limitations, and that each type is more suited to certain tasks and less to others. Because of these reasons, it is becoming common wisdom in the field of mobile robotics to use hybrid maps that integrate several representations, usually of different types. Hybrid maps provide scalability and multiple views, allowing for instance to combine robot-centered and human-centered representations. There is, however, little understanding of the general principles that can be used to combine different maps into a hybrid one, and to make it something more than the sum of its parts. There is no systematic analysis of the different ways in which different maps can be combined, and how they can be made to cooperate. This makes it difficult to evaluate and compare different systems, and precludes us from getting a clear understanding of how a hybrid map can be designed or improved. The investigation presented in this thesis aims to contribute to fill this foundational gap, and to get a clearer understanding of the nature of hybrid maps. To help in this investigation, we develop two tools: The first one is a conceptual tool, an analytical framework in which the main ingredients of a hybrid map are described; the second one is an empirical tool, a new hybrid map that allows us to experimentally verify our claims and hypotheses. While these tools are themselves important contributions of this thesis, our investigation has resulted in the following additional outcomes: • A set of concepts that allow us to better understand the structure and operation of hybrid maps, and that help us to design them, compare them, identify their problems, and possibly improve them; • The identification of the notion of synergy as the fundamental way in which component maps inside a hybrid map cooperate. To assess the significance of these outcomes, we make and validate the following claims: 1. Our framework allows us to classify and describe existing maps in a uniform way. This claim is validated constructively by making a thorough classification of the hybrid maps reported in the literature. 2. Our framework also allows us to enhance an existing hybrid map by identifying spots for improvement. This claim is verified experimentally by modifying an existing map and evaluating its performance against the original one. 3. The notion of synergy plays an important role in hybrid maps. This claim is verified experimentally by testing the performance of a hybrid map with and without synergy.

This thesis deals with the Simultaneous Localisation and Mapping algorithm as it pertains to the deployment of mobile systems in unknown environments. Simultaneous Localisation and Mapping (SLAM) as defined in this thesis is the process of concurrently building up a map of the environment and using this map to obtain improved estimates of the location of the vehicle. In essence, the vehicle relies on its ability to extract useful navigation information from the data returned by its sensors. The vehicle typically starts at an unknown location with no a priori knowledge of landmark locations. From relative observations of landmarks, it simultaneously computes an estimate of vehicle location and an estimate of landmark locations. While continuing in motion, the vehicle builds a complete map of landmarks and uses these to provide continuous estimates of the vehicle location. The potential for this type of navigation system for autonomous systems operating in unknown environments is enormous. One significant obstacle on the road to the implementation and deployment of large scale SLAM algorithms is the computational effort required to maintain the correlation information between features in the map and between the features and the vehicle. Performing the update of the covariance matrix is of O(n�) for a straightforward implementation of the Kalman Filter. In the case of the SLAM algorithm, this complexity can be reduced to O(n�) given the sparse nature of typical observations. Even so, this implies that the computational effort will grow with the square of the number of features maintained in the map. For maps containing more than a few tens of features, this computational burden will quickly make the update intractable - especially if the observation rates are high. An effective map-management technique is therefore required in order to help manage this complexity. The major contributions of this thesis arise from the formulation of a new approach to the mapping of terrain features that provides improved computational efficiency in the SLAM algorithm. Rather than incorporating every observation directly into the global map of the environment, the Constrained Local Submap Filter (CLSF) relies on creating an independent, local submap of the features in the immediate vicinity of the vehicle. This local submap is then periodically fused into the global map of the environment. This representation is shown to reduce the computational complexity of maintaining the global map estimates as well as improving the data association process by allowing the association decisions to be deferred until an improved local picture of the environment is available. This approach also lends itself well to three natural extensions to the representation that are also outlined in the thesis. These include the prospect of deploying multi-vehicle SLAM, the Constrained Relative Submap Filter and a novel feature initialisation technique. Results of this work are presented both in simulation and using real data collected during deployment of a submersible vehicle equipped with scanning sonar.

Randomly scattered sensors may cause sensing holes and redundant sensors. In carrier-based sensor relocation, mobile robots (with limited capacity to carry sensors) pick up additional or redundant sensors and relocate them at sensing holes. In the only known localized algorithm, robots randomly traverse field and act based on identified pair of spare sensor and coverage hole. We propose a Market-based Sensor Relocation (MSR) algorithm, which optimizes sensor deployment location, and introduces bidding and coordinating among neighboring robots. Sensors along the boundary of each hole elect one of them as the representative, which bids to neighboring robots for hole filling service. Robot randomly explores by applying Least Recently Visited policy. It chooses the best bid according to Cost over Progress ratio and fetches a spare sensor nearby to cover the corresponding sensing hole. Robots within communication range share their tasks to search for better possible solutions. Simulation shows that MSR outperforms the existing competing algorithm G-R3S2 significantly on total robot traversed path and energy, and time to cover holes, slightly on number of sensors needed to cover the hole, and the cost of additional messages for bidding and deployment location sharing.

Rugged terrains, including much of the earth's surface, other planets, and many man-made structures, are inaccessible to wheeled and tracked vehicles. This has inspired research into legged vehicles. Prior to the research described here, virtually all legged vehicle designs relied on the concept of mounting actuated leg-type mechanisms onto a single rigid frame or chassis. This dissertation research explores and advances a novel vehicle concept that uses passive legs attached to an actuated multibody structure. This new vehicle moves only its actuated body trunk to achieve locomotion; thus moving in a manner similar to that used by insect larvae known as caterpillars. The passive-legged design is termed a "crawling" vehicle, to differentiate it from "walking" vehicles, which have powered legs. A conceptual design for the proposed vehicle was developed using insights from observations of caterpillar specimen geometry, gaits, leg trajectories, and ranges of motion. The flexible, segmented body of the robot is realized using a series of actuated truss-like mechanisms, resulting in a configuration similar to the body structure of caterpillars. A computer simulation was developed to verify the concept and to assist in creating future designs. This simulation includes a parametric model of the robot structure, an efficient kinematics model, a motion programming method based on six-dimensional parametric cubic trajectories, static stability analysis, actuator velocity and acceleration analysis, wire-frame animations, and rendering, thus providing synthesis and analysis tools for this new class of vehicle. Results of this work show that by using properly designed Stewart-Gough platform mechanisms for the vehicle multibody structure, a range of motion very similar to that of caterpillars is achievable. Simulation tests showed that imitating the caterpillars" primary gait (or stepping sequence) yields superior speed and efficiency, with little reduction of stability, when compared to a simpler, more obvious gait. With proper controls, this crawling vehicle will, like its biological counterpart, be intrinsically stable and have excellent maneuverability over rough terrain. The crawling vehicle is shown to be a viable legged locomotion system that may prove to have superior rough terrain mobility to all previous types of man-made land vehicles. / Ph. D.

This thesis presents an adaptive and reconfigurable mobile robot: the Dual Mobile Robot (DMR). It is driven by two adaptive track-wheel driving modules that combine wheels and tracks to allow real-time interchangeability according to terrain condition. The DMR can automatically convert from a wheel-based robot into a track-based robot by rotating the track-wheel driving modules by 90 degrees, either only tracks or wheels contact with the ground without any interference. It can be driven as a wheel-based robot when operating over a paved road to achieve higher speed and low energy consumption, and as a track-based robot over uneven terrain. In addition, unlike most state-of-the-art mobile robot designs that have an integrated architecture, this design provides a modular architecture which allows modifications and upgrades to be performed via simple replacements or local changes of modules. To establish the modular architecture, this research utilized a unique design paradigm, “Design for product adaptability”. A function-based design process for product adaptability has been conducted in the conceptual design stage. By following the design process, two types of design alternatives of the DMR have been created. After the best product configuration was chosen through evaluation and prioritization, the selected configuration has been implemented by detail design. The DMR prototype was developed and tested to demonstrate its adaptability and advanced mobility functions in real-world environments. The experimental results successfully validated the hypothesis of the proposed robot with its track-wheel interchangeable ability, significantly exceeding the capability of other existing systems.