Novel Space Planning Framework Improves Underwater Mapping Process

By Lina Sorg

Remotely operated vehicles (ROVs), autonomous underwater vehicles, and other undersea robots contribute to continued advances in ocean exploration. These robots contain a variety of sensors and other tools that collect data and contribute valuable insights to otherwise-inaccessible underwater settings. During a minisymposium presentation at the 2023 SIAM Conference on Control and Its Applications, which is currently taking place in Philadelphia, Pa., Brendan Englot of Stevens Institute of Technology presented a space planning framework for robots that utilizes simultaneous localization and mapping to navigate complex, unknown underwater environments. 

Englot and his students have spent the last five years customizing Blue Robotics’  BlueROV underwater robot in order to prototype autonomous navigation and mapping capabilities for accuracy and robustness (see Figure 1). They equipped their custom BlueROV with a variety of hardware—including imaging sonar and an inertial measurement unit—and use it to develop and test new algorithms for sonar-aided autonomous mapping in ports and harbors. The ultimate goal is to maintain high-precision localization throughout a robot’s entire operation and construct an accurate map of the surrounding environment without any prior knowledge.

“We would like to explore and map an unfamiliar environment efficiently while also managing localization uncertainty,” Englot said, adding that his team seeks to understand trajectory’s influence on the mapping process. When setting up their study, they use an occupancy grid to represent the environment, assume that the locations of all landmarks are unknown, and limit belief space planning to a short horizon. 

Englot opened his presentation with a brief overview of some of the existing algorithms and studies that address this scenario, many of which balance pose uncertainty with map information gain. The problem with this strategy is that one ultimately does not know whether the robot is acquiring information about the environment when the pose uncertainty is low; this limitation prevents the direct enforcement of map accuracy. “We did not find a prior method that adequately enforced the construction of an accurate map,” Englot said. He wants the robot to choose the sensing action that drives down the landmark error covariance to the maximum possible degree.

Englot and his colleagues therefore began to build their own framework based on utility functions. They assume that the map is populated with virtual landmarks that could feasibly inhabit every cell on the occupancy grid. As such, Englot wants the robot to take sensing actions that will minimize collective uncertainty of the virtual landmarks that reside in these cells. The resulting expectation-maximization (E-M) algorithm first estimates virtual landmarks based on the history of robot measurements and actions (the “E” step). Given these landmarks, it then selects optimal sensing actions (the “M” step). 

This E-M exploration algorithm—which relies on past measurements and actions as input—follows an established set of steps for each iteration:

• Compute estimated virtual landmark states given past measurements and actions
• Construct candidate paths and propagate robot pose uncertainty along each path
• Evaluate uncertainty of the virtual landmarks that result from each candidate path
• Execute the best path and repeat the previous steps.

The researchers implemented this methodology on a real underwater robot during experimental trials at the U.S. Merchant Marine Academy in Kings Point, NY (see Figure 2). They enclosed the harbor with a bounding box and tasked the robot with a small exploration area to allow for multiple trials; even so, each trial took 45 minutes and boats and other harbor activities frequently interrupted the process. Despite these complications, Englot derived a point cloud map from the robot’s sonar.

He then compared the performance of his team’s proposed E-M algorithm—which examines the virtual map and attempts to reduce the collective covariance that is associated with map cells—to that of next best view planning. Next best view did not achieve the necessary closed loop constraints and caused the problematic buildup of real overlays; in contrast, Englot’s algorithm completed many more closed loop constraints and generated fewer errors in the resulting map. It also exhibited lower pose uncertainty, better map coverage, and a competitive performance in map accuracy — especially because the maintained errors are quite low when compared to other algorithms.

Next steps in this project involve the use of virtual maps as a tool for multi-query path planning scenarios with larger spatial scales. Englot hypothesized that virtual maps could potentially serve as useful costmaps for repeated queries about location uncertainty. “If you’re going to be working in an environment, it’s good to have a virtual map to indicate how uncertain the robot is likely to be in specific regions of the environment,” Englot said. In the resulting trials, virtual maps that act as costmaps performed significantly better than approaches like shortest paths and full belief propagation. In the future, Englot hopes to apply this work to higher dimensional systems and conduct it in three dimensions.

---

References
[1] Wang, J., Chen, F., Huang, Y., McConnell, J., Shan, T., & Englot, B. (2022). Virtual maps for autonomous exploration of cluttered underwater environments. IEEE J. Ocean. Engin., 47(4), 1-20.

Lina Sorg is the managing editor of SIAM News.