Kavraki Lab

Consider the problem of exploring a workspace, sometimes called the watchman route problem. Immediately, this problem can be divided in two different ways: known versus unknown workspaces, and limited versus unlimited visibility. Hoffman, et al (WAFR ‘98) give an online algorithm for guiding a robot in an unknown workspace that produces a path whose length is within a constant factor of the optimal watchman route (the competitive factor is currently 26.5). However, this deals only with unconstrained visibility. Héctor González-Baños and Jean-Claude Latombe (AAAI Fall ‘98) have done excellent work with constrained visibility in unknown workspaces (their “next best view” algorithm).

We are interested in the case of known workspaces and constrained visibility. The ultimate goal is to compute a path for a 6-dof flying robot such that it could inspect a space station for damage or leaks while expending a near-minimal amount of propellant.

Currently, we have a planner producing short (Euclidean length) inspection paths in 2- and 3-dimensional workspaces for point robots with omnidirectional cameras, obeying the two visibility constraints. Some illustrative figures are shown below.


An inspection path computed with no visibility constraints


An example of the maximum distance visibility constraint


The incidence constraint, which rejects “inspection” when the line of sight only grazes the boundary. The red highlights indicate which part of the border is considered “inspected”.


Inspecting a collection of floating objects, with an incidence constraint of 60 degrees. (shown with bounding box for perspective)