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 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?
Overview
The document titled "Area Coverage Path Planning Using Divided Grid-Graphs" presents innovative research conducted by the Jet Propulsion Laboratory (JPL) under NASA's auspices. It focuses on enhancing the efficiency of area coverage observations for Earth-orbiting observation systems, particularly through the use of a novel algorithm for path planning.
The primary architecture discussed is the Eagle-Eye system, which features a framing imager mounted on a movable bus. This bus can be adjusted using a gimbal or by rotating the spacecraft, allowing for flexible observation of adjacent areas. A key advantage of this system is its ability to maintain a specific field of view while the telescope's boresight slowly slews, enabling continuous data collection without the need for extensive settling time. This method significantly increases the efficiency of data gathering, as the telescope's field of view is larger than that of the imager, allowing for strategic division of the areas to be imaged.
The document delves into the complexities of path planning in grid graphs, particularly the challenges posed by the Hamiltonian cycle and path problems, which are known to be NP-complete. The authors introduce a new algorithm that guarantees the existence of a Hamiltonian cycle and can find it in linear time, provided that the grid graph is decomposed into a larger grid by dividing its cells. This approach involves selecting a set of tiles for desired coverage, linking them in concentric paths, and stitching these paths together at designated points.
The research emphasizes the importance of efficient path planning in the context of dynamic surface processes, as it allows for comprehensive imaging of areas that may contain "holes" or gaps. The algorithm's ability to adapt to these challenges makes it a significant advancement in the field of automated planning for space missions.
Overall, this document serves as a technical support package that not only outlines the methodology and findings of the research but also highlights the broader implications for aerospace technology and its potential applications in various scientific and commercial domains. The work is part of NASA's ongoing efforts to leverage innovative technologies for improved observation and data collection in space exploration.
