Mission Planning Based on Dynamic Agent Interaction Graph for Deep Space Probes

Abstract

Facing the increasingly complex deep-space exploration missions and the dynamic space environment, deep-space probes need efficient planning methods for the fast generation of plans. The distribution and concurrency of subsystems make a probe suitable to be modeled as a multi-agent system. Existing multi-agent planners, however, cannot be used directly in mission planning of deep space probes that involve handling numeric constraints such as time resources. To solve the above problem, a multi-agent mission plan-space planning method based on distributed refinement search was proposed. A dynamic agent interaction graph (DAIG) was designed to coordinate interactions between agents during planning. Temporal constraints and resource constraints were modeled as constraint satisfaction problems and were handled by graph theory methods. Experiments show that the method proposed in this paper can save computing time of mission planning problems for a probe with multiple subsystems.

Keywords

deep space probe / multi-agent plan-space planning / numeric constraints

References

[1] BARREIRO J, BOYCE M, DO M, et al. EUROPA: a platform for AI planning, scheduling, constraint programming, and optimization[Z]. ICAPS-12 International Competition on Knowledge Engineering for Planning and Scheduling (ICKEPS). [S. l. ]: ICKEPS, 2012.
[2] FRANK J, JONSSON A. Constraint-based attribute and interval planning[J]. Journal of Constraints Special Issue on Constraints and Planning,2003(8):339-364
[3] MUSCETTOLA N, NAYAK P P, PELL B, et al. Remote agent: to boldly go where no AI system has gone before[J]. Artificial Intelligence,1998(103):5-47
[4] MUSCETTOLA N, FRY C, RAJAN K, et al. On-board planning for New Millennium Deep Space One autonomy[C]//IEEE Aerospace Conference. [S. l. ]: IEEE, 2002.
[5] TRAN D, CHIEN S, SHERWOOD R, et al. The autonomous sciencecraft experiment onboard the eo-1 spacecraft[C]//Autonomous Agents and Multiagent Systems, 2004. [S. l. ]: IEEE, 2004.
[6] CHIEN S, RABIDEAU G, KNIGHT R, et al. ASPEN - automating space mission operations using automated planning and scheduling[C]//In Proceedings of SpaceOps. Toulouse, France: [s. n. ], 2000.
[7] KNIGHT R, RABIDEAU G, CHIEN S, et al. Casper: space exploration through continuous planning[J]. IEEE Intelligent Systems and Their Applications,2001,16(5):70-75
[8] 金颢, 徐瑞, 崔平远, 等. 基于状态转移图的启发式深空探测器任务规划方法[J]. 深空探测学报(中英文),2019,6(4):364-368
JIN H, XU R, CUI P Y, et al. Heuristic search based on state transition graphs for deep space task planning[J]. Journal of Deep Space Exploration,2019,6(4):364-368
[9] 王晓晖, 李爽. 深空探测器约束简化与任务规划方法研究[J]. 宇航学报,2016,37(7):768-774
WANG X H, LI S. Research on constraint simplification and mission planning method for deep space explorer[J]. Journal of Astronautics,2016,37(7):768-774
[10] BRAFMAN R I, DOMSHLAK C. From one to many: planning for loosely coupled multi-agent systems[C]// ICAPS. [S. l. ]: ICAPS, 2008.
[11] ?TOLBA M, KOMENDA A. The MADLA planner: multi-agent planning by combination of distributed and local heuristic search[J]. Artificial Intelligence,2017(252):175-210
[12] TORRE?O A, ONAINDIA E, SAPENA ó. FMAP: distributed cooperative multi-agent planning[J]. Applied Intelligence,2015(41):606-626
[13] TORRE?O A, ONAINDIA E, KOMENDA A, et al. Cooperative multi-agent planning: a survey[J]. ACM Computing Surveys,2017(50):1-32
[14] XU R, CUI P Y, XU X. Realization of multi-agent planning system for autonomous spacecraft[J]. Advances in Engineering Software,2005(36):266-72
[15] DECHTER R, MEIRI I, PEARL J. Temporal constraint networks[J]. Artificial Intelligence,1991(49):61-95
[16] 陈德相, 徐瑞, 崔平远. 航天器资源约束的时间拓扑排序处理方法[J]. 宇航学报,2014,35(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,35(6):669-676
[17] IATAURO M. How does EUROPA solve problems?[EB/OL](2014-10-22)[2021-04-06].https://github.com/nasa/europa/wiki/Bak-Problem-Solving, (accessed 01.10.20).