Significance of Decomposition in Spacecraft Autonomy
Seung Chung, Brian Charles Williams · AIAA Infotech@Aerospace 2010 · 2010
Unlike traditional ight software used in spacecraft, many autonomy software use search algorithms that solve problems with NP complexity or worse. Without exhaustively testing the state space of search algorithms, we can only conclude that the worst case memory or time performance will be exponential or worse. This, however, is unacceptable for missions that are time critical and memory limited. The arti cial intelligence community has also been concerned with the intractability of AI algorithms. As result, a set of decomposition techniques, namely constraint decomposition and causal order decomposition, have been developed to address the issue. Decomposition techniques use a divide-and-conquer approach to divide a problem based on the properties of the problem into a set of simpler subproblems. By decomposing the problem, we are able to determine a tighter bound on the time and memory required to solve the problem and use the decomposition to solve the problem within the guaranteed time and memory. Furthermore, this approach can help design and verify autonomy software. In this paper we review two important decomposition techniques, constraint decomposition and causal order decomposition and their uses within spacecraft autonomy.