Tractable Goal Selection for Embedded Systems with Oversubscribed Resources
Gregg Rabideau, Steve Chien, David I. McLaren · Journal of Aerospace Computing Information and Communication · 2011
We describe an efficient, online goal selection algorithm and its use for selecting goals at runtime. Our focus is on the replanning that must be performed in a timely manner on the embedded system where computational resources are limited (as in many aerospace systems). In particular, our algorithm generates near optimal solutions to problems with fully specified goal requests that can oversubscribe available resources but have no temporal flexibility. By using a fast, incremental algorithm, goal selection can be postponed in a “justin-time” fashion allowing requests to be changed or added at the last minute. This enables shorterresponsecyclesandgreaterautonomyforthesystemundercontrol.Weshowthatthe averagecasecomplexityforupdatingthegoalssetisO(N lgN)andruntimeexecutionisO(N). We perform an empirical analysis on both synthetic data and space operations mission-like scenarios that confirm these performance characteristics. Finally, we show that scaling these performance figures to existing, very limited onboard spacecraft embedded environments (a Mars Reconnaissance Orbiter like environment) appears feasible.