Research on Task Planning Problems for Deep Space Exploration Based on Constraint Satisfaction

Abstract

The ordinary CSP algorithms cannot reflect the characteristics of the task planning progress. How the action rules in task planning for deep space exploration can be mapped into the constraint satisfaction problems is discussed. Based on the conclusion，an action directed constraint is proposed to guide the variable selection procedure in constraint satisfaction problems. Through theoretical analysis，the proposed technology can be used in constraint-programmed planning problem. The simulation experiments show that the algorithm with action guided constraint can effectively reduce the number of constraint checks during the planning procedure and has a better performance on total running time over the standard version. It lays the foundation for the application of the project.

Keywords

planning / constraint satisfaction / variable selection / action-oriented

References

[1] VERFAILLIE G,PRALET C. A timeline,event,and constraint-based modeling framework for planning and scheduling problems[J]. Knowledge Engineering for Planning and Scheduling,2013:61-68
[2] ACHLIOPTAS D，HASSANI S H，MACRIS N，et al. New bounds for random constraint satisfaction problems via spatial coupling[C]//Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms. USA：Association for Computing Machine，2013.
[3] BODIRSKY M. Complexity classification in infinite-domain constraint satisfaction[J]. Eprint Arxiv,2012
[4] MUSCETTOLA N，PANDURANG N P，PELL B，et al. Remote agent：to boldly go where no AI system has gone before[M]. USA：NASA Ames Research Center，1998.
[5] PELL B,BERNARD D,CHIEN S,et al. A remote agent prototype for spacecraft autonomy[J]. Proceedings of SPIE - The International Society for Optical Engineering 2810,1996,28(10):74-90
[6] CICHY B，CHIEN S，SCHAFFER S. Validating the EO-1 autonomous science agent[C]//International Workshop on Planning and Scheduling for Space. Darmstadt，Germany：[s.n]，2004.
[7] SHERWOOD R，GOVINDJEE A，YAN D，et al. Using ASPEN to automate EO-1 activity planning[C]//Proceedings of the 1998 IEEE Aerospace Conference. Colorado：IEEE，1998.
[8] PHILIPPE L. Algorithms for propagating resource constraints in AI planning and scheduling. Existing approaches and new results[J]. Artificial Intelligence,2003,143(2):151-188
[9] FRANK J，JONSSON A，MORRIS R，et al. planning and scheduling for fleets of earth observing satellites[C]//Proceeding of the 6th International Symposium on Artificial Intelligence Robotics，Automation and Space. Montreal：[s.n]，2001.
[10] DUNGAN J，FRANK J，JONSSON A，et al. Advances in planning and scheduling of remote sensing instruments for fleets of earth orbiting satellites[C]//Proceeding of the 2nd Earth Science Technology Conference. Pasadena，CA，USA：Research Institute for Advanced Computer Science （RIACS），2002.
[11] 仲维国,崔平远,崔祜涛. 航天器复杂约束姿态机动的自主规划[J]. 航空学报,2007,28(5):1091-1097
ZHONG W G,CUI P Y,CUI H T. Autonomous attitude maneuver planning for spacecraft under complex constraints[J]. Acta Aeronautica ET Astronautica Sinica,2007,28(5):1091-1097
[12] 程小军,崔祜涛,徐瑞. 几何约束下的航天器姿态机动控制[J]. 控制与决策,2012,27(5):724-730
CHENG X J,CUI H T,XU R. Attitude maneuver control of spacecraft under geometric constraints[J]. Control and Decision,2012,27(5):724-730
[13] 陈德相,徐瑞,崔平远. 航天器资源约束的时间拓扑排序处理方法[J]. 宇航学报,2014,6(6):669-676
CHEN D X,XU R,CUI P Y. A temporal topological sort processing method for spacecraft resources constraints[J]. Journal of Astronautics,2014,6(6):669-676
[14] 伍丽华,陈蔼祥,姜云飞,等. 时态规划中基于CSP技术的时态约束方法[J]. 计算机学报,2012,35(8):1759-1766
WU L H,CHEN A X,JIANG Y F. A CSP-based approach for temporal constraints in temporal planning[J]. Chinese Journal of Computers,2012,35(8):1759-1766
[15] 陈德相,徐文明,杜智远. 航天器任务规划中资源约束的可分配处理方法[J]. 深空探测学报,2015,2(2):180-185
CHEN D X,XU W M,DU Z Y. Dispatchable processing method of resource constraint in spacecraft mission planning[J]. Journal of Deep Space Exploration,2015,2(2):180-185
[16] 赵凡宇,徐瑞. 启发式深空探测器任务规划方法[J]. 宇航学报,2015,36(5):496-503
ZHAN F Y,XU R. Heuristic mission planning approach for deep space explorer[J]. Journal of Astronautics,2015,36(5):496-503
[17] JUDGE M，LONG D. A CSP heuristic for AI planning[C]//Proceedings of 20th Automated Reasoning Workshop. UK：School of Computing，University of Dundee，2013.
[18] PETIT T,BELDICEANU N,LORCA X. A generalized arc-consistency algorithm for a class of counting constraints[J]. IEEE Photonics Technology Letters,2011,24(11):942-944
[19] FRATINI S,POLICELLA N. ICKEPS 2012 challenge domain: planning operations on the Mars express mission[J]. International Competition on Knowledge Engineering for Planning and Scheduling,2012,18(18):195-196