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.
-
[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&or 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. -
点击查看大图
计量
- 文章访问数: 527
- HTML全文浏览量: 53
- PDF下载量: 105
- 被引次数: 0
下载:
