Local Search for Optimal Global Map Generation Using Mid-Decadal Landsat Images


  • Lina Khatib SGT Inc. / NASA Ames Research Center
  • Robert A. Morris NASA Ames Research Center
  • John Gasch Landsat Mission Operations, Goddard Space Flight Center




scheduling, Geo Cover, optimization, local search, mixed initiative, LandSat,


NASA and the United States Geological Survey (USGS) are collaborating to produce a global map of the Earth using Landsat 5 Thematic Mapper (TM) and Landsat 7 Enhanced Thematic Mapper Plus (ETM+) remote sensor data from the period of 2004 through 2007. The map is comprised of thousands of scene locations and, for each location, there are tens of different images of varying quality to chose from. Constraints and preferences on map quality make it desirable to develop an automated solution to the map generation problem. This paper formulates a Global Map Generator problem as a Constraint Optimization Problem (GMG-COP) and describes an approach to solving it using local search. The paper also describes the integration of a GMG solver into a graphical user interface for visualizing and comparing solutions, thus allowing for solutions to be generated with human participation and guidance.

Author Biographies

Lina Khatib, SGT Inc. / NASA Ames Research Center

Dr. Lina Khatib is a senior research engineer and scientist with SGT Inc. at NASA Ames Research Center where, since 1999, she has worked in  the Planning and Scheduling group, Intelligent Systems Division, on various projects in intelligent automation for Space and Earth Sciences. Her Ph.D. is in Computer Science with expertise in Constraint Reasoning and preferences, Heuristic Search, Temporal Reasoning, Intelligent Planning and Scheduling, and Problem Solving.

Robert A. Morris, NASA Ames Research Center

Dr. Robert Morris is a researcher in the automated planning and scheduling group in the Intelligent Systems Division at NASA Ames Research Center. For many years he has served as principal investigator on projects dealing with applying automated information technologies for sensor web coordination. He is currently PI or co-PI on a number of Earth science projects for building applications of automated planning and scheduling technologies. His research interests include representing and reasoning about time, constraint-based planning, and developing search techniques for constraint optimization.

John Gasch, Landsat Mission Operations, Goddard Space Flight Center

John Gasch is a systems engineer at NASA Goddard Space Flight Center, presently as a senior mission analyst for the Landsat Flight Operations Team. Mr. Gasch has contributed to the design and development of numerous mission planning and scheduling systems for NASA and USGS Earth science missions, as well as electronic countermeasures systems for DOD. He received a B.S. in Computer Science from University of Maryland, and an M.S. in Computer Science from Johns Hopkins University. His concentration is on maximizing the utility of Earth Observation remote sensing satellite systems, and improving mission operations efficiency.




How to Cite

Khatib, L., Morris, R. A., & Gasch, J. (2009). Local Search for Optimal Global Map Generation Using Mid-Decadal Landsat Images. AI Magazine, 30(2), 84. https://doi.org/10.1609/aimag.v30i2.2233