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.
- Jeffrey M. Walls, Alex G. Cunningham, and Ryan M. Eustice, "Cooperative Localization by Factor Composition with Faulty Low-Bandwidth Communication Channels." In Proceedings of the IEEE International Conference on Robotics and Automation, Seattle, Washington, May 2015. (pdf)
- Jeffrey M. Walls, and Ryan M. Eustice, "An Origin State Method for Communication Constrained Cooperative Localization with Robustness to Packet Loss" International Journal of Robotics Research 33(9), pp.1191-1208, 2014. (pdf)
- Jeffrey M. Walls, and Ryan M. Eustice, "An exact decentralized cooperative navigation algorithm for acoustically networked underwater vehicles with robustness to faulty communication: Theory and experiment." In Proceedings of the Robotics: Science & Systems Conference, Berlin, Germany, June 2013. (pdf)
- Sarah E. Webster, Jeffrey M. Walls, Louis L. Whitcomb, and Ryan M. Eustice, "Decentralized extended information filter for single-beacon cooperative acoustic navigation." IEEE Transactions on Robotics 29(4), pp.957-974, 2013. (pdf)
- Jeffrey M. Walls, and Ryan M. Eustice, "An origin state method for lossy synchronous-clock acoustic navigation." In IFAC Workshop on Navigation, Guidance and Control of Underwater Vehicles, Porto, Portugal, April 2012. (pdf)
- Jeffrey M. Walls, and Ryan M. Eustice, "Experimental comparison of synchronous-clock cooperative acoustic navigation algorithms." In Proceedings of the IEEE/MTS OCEANS Conference and Exhibition, Kona, HI, September 2011. (pdf)
[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 |
We are currently pursuing belief space planning techniques that consider motion and sensing uncertainty during the planning process.
Email me to request software access.
- Jeffrey M. Walls, Stephen M. Chaves, Enric Galceran, and Ryan M. Eustice, "Belief Space Planning for Underwater Cooperative Localization." In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, Hamburg, Germany, October 2015. (pdf)
- Jeffrey M. Walls, and Ryan M. Eustice, "Toward Informative Planning for Cooperative Underwater Localization." In Proceedings of the IEEE/MTS OCEANS Conference and Exhibition, St. John's, Newfoundland, September 2014. (pdf)
[top]
Puzzles and Games
ClueClue 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:
- Inference: We can pose the 'whodunit' question within both Bayesian estimation and constraint satisfaction frameworks.
- Planning: Given the information already available, where should we move and what questions should we ask to maximally gain information? Or (for extra credit) to dupe other players?
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
- Search: exhaustive guess-and-check (referred to as backtracking if depth-first-search is used).
- Simulated annealing: randomized local-search for combinatorial optimization.
- Loopy belief propagation: maximum a posteriori estimate.
[top]