Research on Extensional Constraint Filtering Method Based on Dynamic Constraint Sets

Abstract

With the development of deep space missions and the complexity of scientific tasks, the autonomous mission planning and scheduling of deep space explorers has become a research hotspot. On the basis of the task characteristics and the analysis of the system constraints of deep space probes,combined the intelligent planning theory with the constraint satisfaction technology,the dynamic characteristics of the constraints in the multi-layer constraint programming model is studied,and the fast extensional constraint filtering algorithm is designed based on the dynamic constraint sets. In this method, the newly added activities are classified according to the conflict between activities in the domain information,and the consistency of variables in the constraint table are checked. The results show that the proposed algorithm can effectively reduce the number of invalid constraints in the constraint processing,reduce the algorithm backtracking in the process of problem processing,and improve the efficiency and success rate of the planning.

Keywords

planning / constraint satisfaction / filtering algorithm / extensional constraint / dynamic constraint set

References

[1] 崔平远,徐瑞,朱圣英,等.深空探测器自主技术发展现状与趋势[J].航空学报,2014,35(1):13-28. CUI P Y,XU R,ZHU S Y,et al. State of the art and development trends of on-board autonomy technology for deep space explore[J].Acta Aeronautica Et Astronautica Sinica,2014,35(1):13-28.
[2] SHEPPERD R,WILLIS J,HANSEN E,et al. DATA-CHASER:a demonstration of advanced mission operations technologies[C]//Aerospace Conference.[S.l]:IEEE,2007.
[3] YANG K K,SUM C C. An evaluation of due date,resource allocation,project release,and activity scheduling rules in a multiproject environment[J]. European Journal of Operational Research,1997,103(1):139-154.
[4] CHIEN S,SHERWOOD R,TRAN D,et al. Using autonomy flight software to improve science return on Earth observing one[J]. Journal of Aerospace Computing,Information,and Communication, 2005,2(4):196-216.
[5] CHIEN S,CICHY B,DAVIES A,et al. An autonomous Earth observing sensorweb[J]. Intelligent Systems,IEEE,2005,20(3):16-24.
[6] KNIGHT R,CHIEN S,KELLER R. Enabling onboard spacecraft autonomy though goal-based architectures:an integration of modelbased artificial intelligence planning with procedural elaboration[C]//IEEE Aerospace Conference. MT,USA:IEEE,2001(1):141-149.
[7] JOHNSTON M. SPIKE:AI scheduling for NASA's Hubble space telescope[C]//Proceedings of 6th IEEE Conference on AI Applications. Santa Barbara:IEEE,1990.
[8] 陈德相,徐瑞,崔平远.航天器资源约束的时间拓扑排序处理方法[J].宇航学报,2014,6(6):669-676. CHEN D X,XU R,CUI P Y. A temporal topological sort processing method for spacecraft resource constrints[J]. Journal of Astronautics, 2014,6(6):669-676.
[9] 陈德相,徐文明,杜智远.航天器任务规划中资源约束的可分配处理方法[J].深空探测学报,2015,2(2):180-185. CHEN D X,XU W M,DU Z Y. Dispatchable processing method of resource constraint in spacecraft mision planning[J]. Journal of Deep Space of Exploration,2015,2(2):180-185.
[10] MUSCETTOLA N. HSTS:integrated planning and scheduling In M. Zweben,and M Fox (eds):intelligent scheduling[M]. Morgan Kaufmann,San Fransciso:Springer,1994:169-212.
[11] SMITH E D,FRANK J,JONSSON K A. Bridging the gap between planning and scheduling[J]. Knowledge Engineering Review,2000, 15(1):166-178.
[12] LI H. Narrowing support searching range in maintaining arc consistency for solving constraint satisfaction problems[J]. IEEE Access,2017,5(99):5798-5803.
[13] JIANG X,XU R. A constraint-programmed planner for deep space exploration problems with table constraints[J]. IEEE Access,2017(5):17258-17270.
[14] MAIRY J B,DEVILLE Y,LECOUTRE C. The smart table constraint[C]//International Conference on AI∨ Techniques in Constriant Programming for Combinatorial Optimization Problems. Switzerland:Springer,2015.
[15] WEI X,YAP R H C. Optimizing STR algorithms with tuple compression[C]//International Conference on Principles and Practice of Constraint Programming. Berlin:Springer,2013.
[16] LHOMME O. A fast arc consistency algorithm for n-ary constraints[C]//National Conference on Artificial Intelligence. USA:AIAA, 2005.