Time Stamped States based Heuristic Algorithm for Spacecraft Mission Planning

Abstract

For real time in deep space exploration, it is a requirement of autonomous mission planning for the explorer to find a plan as soon as possible. A kind of method is to use heuristic algorithm. At the same time, durative actions and numeric information have to be processed. According to these characteristics, this paper adapts planning domain definition language (PDDL) to establish knowledge models and describe time and resource constraints. Then the heuristic algorithm based on condition number is proposed to solve planning problems of deep space exploration. Finally, we compare this heuristic with context-enhanced additive heuristic based on action time in TFD (Temporal Fast Downward) planner. The result of the experiment shows that the heuristic algorithm we proposed is better to solve the planning problems in deep space from the point of view of real time.

Keywords

deep space exploration / heuristic / durative actions / numeric

References

[1] Bonet B, Geffner H. Planning as heuristic search[J]. Artificial Intelligence, 2001,129:5-33.
[2] Edelkamp S, Schrödl S. Heuristic search: theory and application [M]. United States of America: Margan Kaufmann, 2011:1-427.
[3] Cushing W, Kambhampati S, Mausam,et al. When is temporal planning really temporal? [C]//The International Joint Conference on Artificial Intelligence. Hyderabad, India:[s.n.], 2007.
[4] Haslum P, Geffner H. Heuristic planning with time and resources[C]//Proceedings of the Sixth European Conference on Planning. Toledo, Spain:[s.n.], 2001.
[5] Minh B D, Kambhampati S. Sapa: a multi-objective metric temporal planner[J]. Journal of Artificial Intelligence Research, 2003,20:155-194.
[6] Helmert M, Geffner H. Unifying the causal graph and additive heuristics[C]//Proceeding of the 18th International Conference on Automated Planning and Scheduling(ICAPS). Sydney, Australia: [s.n.], 2008.
[7] 彭婷.基于修复策略的深空探测器自主任务规划方法研究[D].北京:北京理工大学,2012.[Peng T. Autonomous mission planning method of deep space explorer based on repair planning strategy[D]. Beijing:Beijing Institute of Technology, 2012.]
[8] Fox M, Long D. PDDL2.1: an extension to PDDL for expressing temporal planning domains[J]. Journal of Artificial intelligence research, 2003,20:61-124.
[9] Smith B, Sherwood R, Govindjee A, et al. Representing spacecraft mission planning knowledge in ASPEN[C]//Artificial Intelligence Planning Systems Workshop on Knowledge Acquisition. Pittsburgh: [s.n.], 1998.
[10] 饶东宁,蒋志华,姜云飞.规划领域定义语言的演进综述[J].计算机工程与应用,2010,46(22):23-25.[Rao D N, Jiang Z H, Jiang Y F. Review on evolution of planning domains definition language[J]. Computer Engineering and Applications, 2010,46(22):23-25.]
[11] Helmert M. The fast downward planning system[J]. Journal if Artificial Intelligence Research, 2006(26):191-246.
[12] Eyerich P, Mattmüller R, Röger C. Using the context-enhanced additive heuristic for temporal and numeric planning[C]//Proceeding of the 19th International Conference on Automated Planning and Scheduling (ICAPS). Thessaloniki, Greece: [s.n.], 2009.