Planning area coverage observations is a challenge in an architecture with a framing imager affixed to a bus that can be moved, and a mirror or other device that allows for small, but fast, observation of adjacent areas along the boresight of a telescope. The telescope boresight can slew slowly while the mirror system maintains pointing on a specific field of view. This allows the continuous gathering of data (much like push - broom instruments) without the need to slew or settle. Since the telescope field of view is much larger than the imager field of view, the areas to be imaged can be divided into quarters.

The problem is transformed into a gridgraph problem, and is further reduced to a 2×2 decomposition. Determining if a solid grid-graph has a Hamiltonian cycle is polynomial, but that is insufficient here as there is always an option of picking up and moving to a different part of the graph. Areas that need to be covered are not guaranteed to be free of “holes.” A new algorithm is introduced that guarantees a Hamiltonian cycle and finds it in linear time, given a decomposition of any grid-graph into a larger grid-graph, by dividing the cells along each dimension.

This technique relates to any mapping system that uses a bus that is decomposed into a primary telescope and steerable focal plane, where the focal plane is a framing system and the goal is to collect data on areas that are greater than accommodated by a single focal plane data take.

This work was done by Russell L. Knight of Caltech for NASA’s Jet Propulsion Laboratory.

This software is available for commercial licensing. Please contact Dan Broderick at This email address is being protected from spambots. You need JavaScript enabled to view it.. Refer to NPO-49422.

This Brief includes a Technical Support Package (TSP).
Area Coverage Path Planning Using Divided Grid-Graphs

(reference NPO49422) is currently available for download from the TSP library.

Don't have an account? Sign up here.

NASA Tech Briefs Magazine

This article first appeared in the October, 2015 issue of NASA Tech Briefs Magazine.

Read more articles from this issue here.

Read more articles from the archives here.