Projects

Several projects that I have worked on for both research and fun are described below. In general, my PhD research has focused on consistent bounded error underwater navigation. Overall, these projects span control, estimation, optimization, and machine learning. Code for a few of the projects is available on my Github page.

[Cooperative localization]
[Informative planning]
[Puzzles and Games]


Low-bandwidth cooperative localization

Underwater vehicles typically integrate body-frame velocity and world-frame attitude measurements to compute a dead-reckoned navigation solution. Unfortunately, position error grows unbounded in time without access to global position references such as GPS (unavailable while subsea) or long-baseline acoustic networks.

Vehicles can observe relative range between each other by measuring the time-of-flight of acoustic communication signals. We focus on how to consistently incorporate relative range information in distributed estimation frameworks using the available communication bandwidth; teamwork for underwater vehicles.

Server vehicles (left) support clients (right).

Solving for the maximum a posteriori estimate is trivial in the centralized estimator, \[\begin{align} X_c^* &= \arg \max_{X_c,X_s} P (X_c,X_s|Z_r) , \end{align}\] where \(X_c\) and \(X_s\) are the sets of client and server poses, respectively, and \(Z_r\) is the set of OWTT observations. Distributing the estimation problem is difficult because the number of pose variables increases with time and we have constant (and quite small) bandwidth.

Our earliest work focused on enabling vehicles with good navigation (servers) to support vehicles with poor navigation (clients) under several assumptions limiting communication topology and information construction. These assumptions have allowed us to leverage the structure of the underlying least-squares problem to limit communication broadcasts to small and constant sized data packets.

We are now working on methods that exploit the factor-level structure of the problem (as opposed to the information-level) in order to robustly distribute local information throughout the network. We can now simultaneously treat all vehicles as servers and clients and more closely derive the full benefit of the cooperative network.

Since 2010 I have had the opportunity to extensively participate in fielding two Ocean Server Inc. Iver2 AUVs at the University of Michigan. Each vehicle is outfitted with an advanced dead reckoning sensor suite including: a 600kHz RDI Explorer DVL, a Microstrain GX3-25 stabilized attitude reference, and a KVH-3000 fiber-optic gyro. We use 25kHz WHOI micromodem for acoustic communication with a custom low-drift clock reference to maintain synchronous time.

Email me to request software access.


[top]

Informative path planning

As above, we are interested in enabling teams of underwater vehicles to effectively localize each other using relative range constraints derived from acoustic time-of-flight observations. The quality of the localization solution is inherently dependent on the relative geometries between participating vehicles. We are interested in efficiently computing optimal relative vehicle trajectories to minimize navigation uncertainty (or equivalently maximize information). We believe that cooperative localization networks can reduce navigation errors to rival the performance of long-baseline acoustic networks.

Poor relative geometry Better relative geometry
Formally, we would like to compute a server path, \(\mathcal{P}\), that maximizes an information objective \[\begin{align} \mathcal{P}^* &= \arg \max_{\mathcal{P} \in \Psi} I (\mathcal{P}) \\ \text{subject to: } & c (\mathcal{P}) \leq B, \end{align}\] where \(c (\cdot)\) and \(B\) represent the cost of a path and a budget, respectively. If we consider a discrete search space \(\Psi\), this problem is NP-hard. Our current work is focused on efficiently finding optimal (or guaranteed near-optimal) solutions.

We are currently pursuing belief space planning techniques that consider motion and sensing uncertainty during the planning process.

Email me to request software access.


[top]

Puzzles and Games

Clue

Clue is a simple board game where we can easily apply a few fun algorithms. In particular, we are interested in two aspects of the game:

Incredibly, these problems overlap substantially with our cooperative underwater navigation work. In this case, however, we are interested in the discrete distribution over possible game 'states'. Although there are only 6x9x6=324 possible ways to choose the guilty suspect, location, and weapon, there are billions to trillions of different ways to deal the full game depending on the number of players. This curse of dimensionality makes inference an interesting challenge.

Sudoku

Sudoku is a captivating (but in many ways, mindless) puzzle that requires solving a constraint satisfaction program. The rules are simple: fill a 9x9 grid with digits 1-9 such that each row, column, and block contain all digits exactly once given the value of several squares a priori. Much as with Clue, we can frame this challenge as a constraint satisfaction problem or Bayesian inference.

There are on the order of \(10^{21}\) unique Sudoku configurations (Felgenhauer and Jarvis, 2005). This is a huge search space. Indeed, the general Sudoku solution is NP-complete. Most puzzles, however, can generally be solved quite quickly. Several research articles have discussed efficient algorithms for solving Sudoku puzzles. Chi and Lange (2012) provide an excellent overview of several combinatorial algorithms including a few described here. We have employed a few different strategies to solve sudoku puzzles, including

Initial python code is available on Github.

[top]