This paper presents a planning algorithm suitable whenever n objects must be collectively characterized by m observers and their relative motions are known a priori. This situation arises in Space Situational Awareness (SSA) problems due to the fixed orbits of spacecraft, and also occurs in several other aerospace and manufacturing environments. The new algorithm is a synthesis of two standard methods used to solve combinatorial optimization problems arising from various large-scale constrained active sensor planning applications. The algorithm allows constituent techniques to operate in domains where they perform better. Both constituent methods, Integer Linear Programming (ILP) Relaxation and a Batch-Greedy algorithm, are elaborated in detail. A very powerful feature of the overall approach is that an upper bound on the gap between the found sub-optimal solution and the unknown optimal solution is available. The ILP-relaxation algorithm provides an optimal but physically unrealizable solution, so if realizable performance approaches that of the ILP-relaxation solution, then the sub-optimal solution is very nearly optimal. A visual inspection problem for SSA, which lies in the strongly NP-hard class, is considered and it has been shown that the mixed method yields very nearly optimal solutions in polynomial time. Simulation results confirm the effectiveness of the proposed planning method on different orbits, including Low Earth and geosynchronous orbits.
展开▼
