A mark-based hierarchical asynchronous temporal constraints reasoning algorithm for multi-agent mission planning

The establishment of a lunar base requires the collaborative cooperation of multiple lunar rovers. The efficiency of rovers’ mission planning can be increased by quickly determining whether the numerous temporal constraints between the activities of rovers are consistent. This research focuses on constructing a new and efficient algorithm to solve the complex temporal constraint problem in mission planning for lunar rovers. A mark-based centralized arc-consistency algorithm is proposed to filter unnecessary constraint checks depending on whether the mark of each variable changes. It improves computational efficiency and we prove the rationality of the algorithm theoretically. Then, based on the algorithm mentioned above, a mark-based hierarchical asynchronous algorithm is proposed to reduce the iterations of temporal constraints reasoning through asynchronous computation. At the same time, each rover tightens its local variables’ domains to a minimum before interacting with other rovers, which reduces the impact of locally shared variables on the outside. This avoids the problem of reduced computational efficiency caused by the waiting time of asynchronous computing. Finally, we conduct comprehensive experiments on different types of benchmark datasets, and the results show that the mark-based hierarchical asynchronous algorithm can improve efficiency by up to 47.64 % and reduce the number of constraint checks by up to 89.26 % compared to existing algorithms, which also benefits to reduce the number of communication messages and iterations.