Neil Mathew - University of Waterloo

Research

My research is currently focused on the following areas.

Cooperative Delivery Planning

This research addresses a team of cooperating vehicles performing autonomous deliveries in urban environments. The cooperating team comprises two vehicles with complementary capabilities, a truck restricted to travel along a street network, and a quadrotor micro-aerial vehicle of capacity one that can be deployed from the truck to perform deliveries. The problem is formulated as an optimal path planning problem on a graph and the goal is to find the shortest cooperative route enabling the quadrotor to deliver items at all requested locations.
The work was published in the Workshop on the Algorithmic Foundations of Robotics, 2014

Autonomous Exploration and Sample Return

This work on coverage path planning was done was as part of the NASA Sample Return Robot Challenge 2013 held at Worscestor Polytechnic Insitute. The challenge requires competitors to develop an autonomous rover weighing less than 80 kg, capable of searching an unknown 80,000 m² area for 10 known samples in under 2 hours, at a maximum speed of 2 m/s. No GPS or magnetometer measurements are to be relied on. The test platform designed for this competition is in the image roll banner . In 2013, UW was one of only two teams that were able to complete the challenge. Unfortunately we didn't win because of a small technicality with the placement of the sample on the home base. But it made for a really thrilling experience!

Convex Decomposition for Coverage

The objective of coverage is to generate a path for a robot to pass a given sensor footprint over all areas of a search environment with a guarantee that no areas will be left unvisited. The approach in this work is to use an optimal convex decomposition (OCD) to reduce the environment to a set of convex regions that can be searched using simple sweep patterns.

The purpose of convex decomposition is to generate sectors of the map that locally guarantee line of sight within each sector area. While this property is necessary to generate feasible sweep patterns in any direction, it is also important for dynamic online planning to limit the replanning frequency with the assumption that the convex sector closest to the robot is completely unoccluded prior to executing coverage.

We present an approximation algorithm to the OCD that outperforms existing decomposition algorithms in our paper published in the Journal of Field Robotics

Robust Coverage Path Generation

The notion of coverage investigated in this work involves using two sensor modules, namely mapping and vision based object detection to navigate and search an environment for samples. The mapping module generates a 2D drivability map using a laser scanner with a large sensor footprint of 75 m radius. The path planner must generate a path to search the environment as identified by the map by passing a smaller camera sensor footprint of approximately 3 m radius over every point in the search space. The planning process must be consistently updated as new map and visual information becomes available.

Given the set of map sectors to cover (above), the second stage involves generating an optimal coverage path through all the internal sectors. The optimality of the path depends on the order in which sectors are visited, the structure of the coverage pattern within each region, and the entry and exit points used to link successive sectors.We formulate the problem as a discrete path planning problem on a graph abstraction of the environment and present heuristic algorithms to obtain near optimal solutions.

Here are some pictures from our latest NSRRC Competitions.

Persistent Surveillance

Coordinated teams of autonomous robots are often proposed as a means to continually monitor changing environments in applications such as air quality sampling, forest fire or oil spill monitoring and border security. But the challenge with using autonomous robots in persistent tasks is that mission durations generally exceed the run time of the robots, and in order to maintain continuous operation they need to be periodically recharged or refuelled.

Multi-robot Rendezvous for Autonomous Recharging

This work introduces multi-robot path-planning strategies for recharging autonomous robots performing a persistent task. We consider the case of long-term monitoring missions performed by a team of UAVs. The proposal is to introduce a separate team of dedicated charging robots that the UAVs can dock with in order to recharge and ensure a continued operation. To this end, we plan optimal paths for the charging robots such that they rendezvous with and recharge all the UAVs as needed. Using a sampling based roadmap approach, the UAV trajectories are discretized into sets of charging locations and a roadmap graph subject to timing constraints is defined over them. Solutions consist of optimal paths through the graph for each of the charging robots. Further, we extend the problem to solve the periodic recharging problem that generates a comprehensive optimal schedule for recharge rendezvous over a planning horizon.

For more information, see our work on Multi-robot Rendezvous for Recharging in Persistent Tasks.

Heuristic Algorithms for the Generalized Travelling Salesman Problem

Our work on Multi-robot rendezvous got me interested in general optimal routing problems. In the autonomous recharging work, we formulate the rendezvous problem as a Generalized Travelling Salesman Problem and solve it using the Noon-Bean Transformation to first convert it to the TSP and then find a solution using TSP heuristic algorithms. Unfortunately the Noon-Bean transform only allows for the computation of a single GTSP path and is not scalable to the multi-robot case. We have developed novel modifcations to the Noon-Bean Transformation to adapt it to the Multiple Generalized Travelling Saleman case and employ to to compute rendezvus paths for an entire team of charging robots.

For more information, see our work on Graph-based Multi-robot Rendezvous Planning.

Energy-aware Coverage Control for UAV teams

This work was done as an extension of previous work by Jason Derenick, Nathan Michael and Vijay Kumar on Energy-aware coverage control with docking for robot teams. Prior to their work, Cortes et al. employ Lloyd's algorithm to develop a centroidal Voronoi tessellation-based controller that optimally covers a convex area with a team of mobile robots. Derenick et al. propose a modification that introduces a combined coverage and energy dependant control law to drive each robot towards a fixed docking station as their energy levels become critical. However their work only considers static charging stations and no charge scheduling to ensure minimal hindrances to the coverage objective.

To mitigate this, our work proposes the idea of mobile charging stations and uses a two-layer centroidal Voronoi tessellation to enable UAVs and UGVs to rendezvous in a scheduled manner when UAV energy levels become critical.

UAV Autopilot Module

The UWMAV Autopilot project was a research project undertaken as part of the University of Waterloo Micro-Aerial Vehicles Team. The scope of this project involved the design of a modular autopilot platform for versatile use on any UAV platform. The goal was to build a single PCB module to integrate a Gumstix Overo and NXP microcontroller with a Camera, GPS, IMU and Altimeter to perform estimation, control, and image processing all on one module. Though we didn't get as far as we had hoped, we managed to develop a full estimation and perception suite as part of an undergraduate design project. I also won the ASME Award for the best technical design project in 2010 .

Vision-based Alignment for Hip Replacement Surgeries

This project involved developing a monocular camera based alignment system for surgeons performing hip replacement surgeries. A system of infra-red LED's was used to estimate and track the 3D position and orientation of a hip-implant tool with respect to the initial femoral allignment in the pelvis. The accuracy of the system was tested using the Optitrack Motion Capture System, in lighting conditions typical of operation theatres. The project was undertaken in a collaboration between the University of Waterloo and Avenir Medical, a Waterloo company that develops intelligent surgical equipment..