Keywords

1 Introduction

Satellite systems based on small spacecrafts for Earth remote sensing (ERS) belong to a new generation of space observation systems (SpOS) designed to obtain images of the earth’s surface in various spectral ranges. The obtained data is more and more in demand in various areas of human activity, such as military, forestry and agriculture, cartography, climate research, disaster recovery operations, etc. [1]. Thus, there is a need to build up the ERS orbital group and put into operation a large-scale constellation of small spacecrafts along with traditional large-mass ones. Depending on the task of SpOS, they can vary from several dozens [2] to hundreds [3, 4] of satellites. Consequently, the number of ground stations for receiving and transmitting information (GS) also increases. They are part of the ground complex for servicing the orbital group.

To ensure targeted functioning of the space observation system, it is required to solve the problem of planning execution of incoming imaging applications, which is an NP-complete task [5]. At the same time, large-scale orbital constellations impose much more rigid requirements on methods and means of planning in comparison with traditional single ERS satellites. Among the main requirements are the following [6]:

  • scalability: planning thousands of applications on a significant horizon without losses in processing speed with a growing number of applications and resources;

  • adaptability: changing plans according to incoming events in a mode close to real time without stopping and completely recalculating the schedule;

  • flexibility: taking into account individual characteristics of applications and resources to build the most optimal solution for multi-criteria optimization;

  • efficiency: the time for placing new applications should be measured in minutes;

  • reliability and survivability: in case of failure of some of the SpOS resources.

Most of existing developments such as SaVoir [7], STM [8], STK Scheduler [9], etc. are centralized, monolithic, hierarchical and sequential solutions. They only partially satisfy requirements, which makes them poorly applicable for large-scale SpOS. Thus, there is a need either for serious revision of existing software and algorithmic solutions, taking into account the emerging requirements, or for development of new approaches to planning orbital groups, taking into account domain semantics more deeply.

One of such approaches to resource management in complex systems is the use of virtual market methodology based on multi-agent technology (MAT) [10, 11], allowing flexible adaptation of schedules by events in real time. MAT also takes into account individual characteristics of orders and resources. The model of demand-resource network (DR-network) helps create high-performance, distributed, fault-tolerant solutions for resource management of SpOS in comparison with traditional methods.

The purpose of this work is to present the implementation and experimental study of a two-stage hybrid method for planning large-scale SpOS: 1st stage - building an initial plan using a greedy optimization algorithm (conflict-free planning); 2nd stage - multi-agent adaptation and optimization (proactive planning).

This approach develops the initial solution [12, 13] by improving architecture of multi-agent system (MAS) and introducing additional heuristics, significantly reducing complexity of combinatorial search for a solution for virtual market and DR-networks.

The second section of this paper proposes a SpOS model and formulation of the planning problem. Section 3 provides an overview of the current state of solutions. The fourth section describes the developed adaptive scheduling method. Section 5 examines a prototype SpOS planning system and presents experiment results. Section 6 provides a conclusion on development and application of the described solution.

2 The Problem of Planning Space Observation Systems

2.1 Model

The SpOS model consists of a set of small spacecrafts Sat = {sati}, i = \(\overline{1,L }\) and a set of ground stations \(GS = \left\{ {gs_{j} } \right\},r = \overline{1,G}\). Each sati spacecraft has its own orbit Oi (the orbits of satellites can be located both in one plane, and in different planes; in the first case they have a similar trajectory), limiting roll angle maxRollAnglei and pitch angle maxPitchAnglei, as well as parameters of imaging equipment (f - focal length, matx - matrix dimensions, minimum angle of sun elevation minSunAnglei, memVoli memory capacity). And each gsj is characterized by geographic location coordj and parameters of antenna (opening angle and data reception rate). The composition of spacecrafts and GS may change over time. Each satellite may have restrictions for data transfer to a certain GS. Besides, time intervals of inaccessibility can be indicated.

The targeted functioning of SpOS consists in execution of a set of applications \(R = \left\{ {r_{p} } \right\},p = \overline{1,P} .\) The rp application can have its priority prp and restrictions (execution period \(t_{p} = [t_{p}^{start} ;{ }t_{p}^{end} ]\), admissible image linear resolution minRp and maxRp and admissible sun angle minSunAnglep and maxSunAnglep). Besides, \(R\) can also change.

In the described model, two operations are performed:

  • imaging of the observation object (OO), characterized by execution interval \(t_{p}^{imag} = [t_{p}^{imagStart} ;{ }t_{p}^{imagEnd} ]\), roll and pitch angles rollAnglep and pitchAnglep.

  • transfer of the images dropp, characterized by execution interval \(t_{p}^{drop} = [t_{p}^{dropStart} ;{ }t_{p}^{dropEnd} ]\) and data transmission speed baudRatep.

2.2 Problem Statement

It is necessary to provide adaptive scheduling of incoming applications, redistributing them between spacecrafts in order to increase the SpOS productivity, obtain images of the highest quality, minimize the lead time for individual orders and ensure fulfillment of other criteria. The system’s objective function (OF) has the following form:

$$ OF = \frac{1}{S}\mathop \sum \nolimits_{k = 1}^{N} OF_{k} \to max, $$
(1)
$$ OF_{k} = \mathop \sum \nolimits_{m = 1}^{M} c_{m} F_{m}^{k} \to max, $$
(2)

where

  • \(OF\) is the system’s objective function,

  • \(OF_{k}\) – is the OF of the k-th application,

  • S is the total number of applications,

  • N is he number of placed applications,

  • M is the number of optimization criteria,

  • cm is the weighting factor of the m-th optimization criterion, such that \(0 \le c_{m} \le 1,\mathop \sum \limits_{m = 1}^{M} c_{m} = 1 \),

  • \(F_{m}^{k}\) is evaluation of the m-th optimization criterion for the k-th application.

Minimization of the imaging time \(F_{1}^{k}\) (3) and maximization of image quality \(F_{2}^{k}\) (4) are chosen as optimization criteria.

$$ F_{1}^{k} = \frac{{t_{k}^{end} - t_{k}^{imagEnd} }}{{t_{k}^{end} - t_{k}^{start} }}, $$
(3)
$$ F_{2}^{k} = \frac{{minR_{k} - r\left( {f,{\text{matx}},{ } {\text{rollAngle}}_{k} ,{\text{pitchAngle}}_{{\text{p}}} } \right)}}{{minR_{k} - maxR_{k} }}, $$
(4)

where r is the function for linear resolution of the image for the k-th application [14].

3 State of the Art Review

Various classical and metaheuristic optimization algorithms are proposed for solving the problem of planning space imagery. Application of machine learning (ML) methods is also studied. One of the most famous metaheuristic algorithms is the ant colony one [15, 16]. Other equally popular algorithms are the local search method [17, 18] and the genetic algorithm [19, 20]. Heuristic and metaheuristic algorithms show higher performance in comparison with traditional optimization methods, however, heuristics requires strict specifications for problem conditions. Meanwhile, operation time and quality of obtained solutions can strongly depend on the initial data. Attempts of using ML methods are described in [21,22,23]. ML has great potential because it allows for training on data but does not require users to hard-code parts of the algorithm. However, ML algorithms currently have limited interpretability (e.g., there is no way to explicitly specify constraints) and require quite a large amount of data for training.

Recently, approaches to planning ERS data using agents have begun to develop [24,25,26]. The planning process proposed in [24] consists in interaction between agents of the survey strip and agents of the spacecraft. It is based on heuristics of programming in constraints together with virtual market approach. Results of its comparison with the currently used greedy algorithm show advantages of the proposed approach. However, performance of this solution is still insufficient for the task proposed in this paper. [25] describes the mechanisms of market auctions for distribution of orders for OO imaging between spacecrafts. They are operated by their own mission centers, coordinating their schedules using auction protocols, bidding on vacant orders based on the influence on the onboard plan and forecasted profits. [26] discusses the idea of ​​fully autonomous planning on board a spacecraft. Its main advantages lie in using the current actual data on the state of the spacecraft and its resources to respond to emerging events in real time. However, in order to create a full-fledged MAS using a spacecraft in orbit, it is necessary to overcome limitations of the computing capabilities of onboard equipment. It is also important to build a stable communication system with several spacecrafts.

Complexity and dynamics of the market of ERS services leads to the fact that traditional, centralized, hierarchical and sequential methods based on heuristic algorithms do not effectively solve the problem of adaptive resource management for large-scale SpOS with acceptable quality and within the required time. A promising area is the use of methods and algorithms based on artificial intelligence and an agent-based virtual market, taking into account the domain semantics, conflict analysis, non-deterministic behavior, self-organization and adaptation in real time. However, currently these methods are at the stage of initial development, therefore, integral solutions, suitable for practical digital implementation, have not yet been designed and implemented [26, 27].

4 Adaptive Planning Method

Figure 1 shows a diagram of the adaptive planning method, which consists of preparing initial data (visibility intervals and placement options) and hybrid scheduling, combining a greedy optimization algorithm (conflict-free scheduling) with multi-agent adaptation and optimization (proactive scheduling).

Fig. 1.
figure 1

Diagram of the adaptive planning method

Full size image

Before planning is initiated, calculation of the satellite-GS and satellite-OO visibility intervals is performed on the specified planning horizon [\( t_{min}^{start} ,t_{max}^{end}\)]. Next, possible placement options pok for each application are calculated. The possible placement option is a combination of both visibility intervals within which imaging and dropping operations can be performed. The exact operation time is determined during planning.

Calculation of possible placement options is implemented based on the method of successive concessions between optimization criteria. A sequence of possible placement options is formed, sorted in descending order of objective functions of applications (2). The first place is for the placement option at the global optimum point.

4.1 Conflict-Free Planning

At this stage, an initial feasible schedule is constructed using a greedy optimization algorithm. The quality of the schedule does not really matter. The purpose is to form an initial state for the next stage of proactive planning. Applications occupy the first vacant placement option, without trying to displace those that are already allocated.

Algorithm 1 presents the pseudocode for conflict-free planning method. The list of applications is organized and grouped according to the value of the prp priority (lines 1–2). Then, for each group of applications, an attempt of planning is made (line 4–11). Options for placing each application are sequentially sorted out (line 7–11). For the next option, a search is performed for specific intervals of imaging and transmitting operations within the specified visibility intervals (line 8), for which there are no conflicts with other previously placed applications. If such intervals are found, the imaging job is formed (line 10–11). Otherwise, the algorithm proceeds to the next placement option.

figure a

4.2 Proactive Planning

At this stage, the resulting schedule is optimized using a multi-agent approach, which consists in competition and cooperation of agents with certain resources or demands [12]. Agents interact via negotiations on the virtual market through mutual compromises and concessions and arrive at a locally optimal solution.

Two types of agents are introduced: an application agent with the goal of occupying the most advantageous placement, and a scene agent, designed to control the activity of application agents and interact with external systems. The application agent is responsible for making changes to the schedule: it can move another agent from a more advantageous position or change its own position upon the request of another agent. To assess the current position of an agent, its satisfaction function \( SF_{k} \left( {po_{k} } \right)\) (5) is used, which is the difference between the value of the task’s OF (2) at the global optimum point \(OF_{k} \left( {po_{k} } \right)\) and the OF value for the current accommodation option \(OF_{k} \left( {po_{k} } \right)\):

$$ SF_{k} \left( {po_{k} } \right) = 1 - \left( {OF_{k} (p\dot{o}_{k} ) - OF_{k} \left( {po_{k} } \right)} \right). $$
(5)

During proactive planning, the scene agent grants the proactive right to application agents, starting with those with the least advantageous position (\(SF_{k} \left( {po_{k} } \right) = min\)).

Figure 2 shows the negotiation protocol of agents during proactive planning.

Fig. 2.
figure 2

Negotiation protocol at the stage of proactive planning

Full size image

An agent that is launched for proactivity acts according to the following algorithm:

  1. 1.

    Sequentially search through placement options that are better than the current one.

  2. 2.

    For the next placement option, determine the list of conflicting applications and send a message to their agents with a proposal to find another placement, using compensation equal to the increment of the agent’s OF \(\Delta F = F_{j} \left( {\widetilde{po}_{j} } \right) - F_{j} \left( {po_{j} } \right)\). Upon receipt of this message, the agent of the conflicting application Rc recursively searches for another placement option using a similar algorithm (embedded proactivity) and sends its solution in a response message. It indicates the agent’s willingness to change its position in the schedule and the \(\Delta F_{c}\) losses in case of agreement.

  3. 3.

    If all agents of conflicting applications agree to move, the total losses \(\mathop \sum \nolimits \Delta F_{c}\) are evaluated, and if the agent of a proactive application can compensate for them due to the increase of its OF, i.e. \(\Delta F > \mathop \sum \nolimits \Delta F_{c}\), the resulting permutation is applied.

  4. 4.

    Otherwise, the application agent proceeds to the next placement option (point 1).

The schedule is synthesized until, during the next planning iteration, none of the application agents can occupy a more advantageous position. This means achievement of the local optimum of the system’s OF. After that, the constructed schedule is saved.

It is important to note that the state of the system is not static. The data may be subject to changes due to arrival of new events. In this case, part of the constructed schedule may become irrelevant and adaptively adjusted by conducting new negotiations between the application agents without stopping and restarting the system.

5 Software Implementation and Experimental Studies

To test the applicability of the proposed approach to solving the problem of planning large-scale SpOS in real time, its software implementation has been created in the form of a prototype of a multi-agent system for planning the targeted use of SpOS (Fig. 3). This prototype has been then used for a number of experimental studies.

Fig. 3.
figure 3

System user interface

Full size image

The prototype has a client–server network architecture. The server side of the system is written in Java using the Spring framework. The user interface is a one-page web application through which the initial data is loaded and modified (spacecrafts, GS, applications, calendars, resource availability restrictions, etc.). The interface also helps manage the planning progress, monitor resources, view reports and planning results.

5.1 Investigation of the Method’s Performance and Ability to Adapt the Schedule

This study evaluated performance of the presented method and its ability to adapt the schedule damaged by failure of one of the spacecrafts. During the experiments, the scheduling of applications for OO imaging has been carried out first, the number of applications varied from 100 to 20,000 for a different number of small spacecrafts (15, 25, or 35). The system’s OF value (1) (Fig. 4a) and the planning time (Fig. 4b) were measured. Then, one of the spacecrafts was excluded from the system and the time spent on restoring the solution was also measured (Fig. 5). The experiments were carried out on a PC with a 4-core CPU Intel Core i7-3770 and 8 GB RAM. The number of GS in all experiments was the same - 20. The planning horizon was 21 days.

Experimental results have shown that the developed method meets performance requirements when working with large volumes of applications. In this case, the quality of the obtained solution weakly depends on the number of small spacecrafts and applications in the system. The time spent on restoring a schedule damaged by failure of one of the spacecrafts is a much smaller fraction of the total planning time and increases proportionally with the growing number of applications and spacecrafts. Comparison of the obtained results with those presented in [12, 17, 24] shows that the developed algorithm demonstrates higher performance and scalability, allowing for a similar time interval to process a much larger number of incoming applications (by 5–10 times).

Fig. 4.
figure 4

Graphs of dependence of the OF value (a) and the planning time (b) on the number of applications and spacecrafts in the system

Full size image
Fig. 5.
figure 5

Graphs of dependence of the schedule recovery time on the number of applications and spacecrafts in the system

Full size image

5.2 Comparison with Centralized Scheduling Algorithms

In this study, the effectiveness of the developed method has been analyzed in comparison with centralized scheduling algorithms based on traditional optimization methods, such as the simulated annealing algorithm and the Tabu Search algorithm, implemented in the Optaplaner open-source Java scheduling framework. They have been compared based on the quality of the resulting schedule and the time required for its compilation.

In the course of the study, a series of experiments have been carried out, in which the number of applications for OO imaging varied from 100 to 5000. At the same time, the time spent on drawing up the schedule and the system OF value have been measured (1). The PC configuration and the number of ground stations are similar to the previous experiment, the number of spacecrafts is 25. Based on the results of the experiments, graphs of dependence of the system OF value (Fig. 6a) and the planning time (Fig. 6b) on the number of applications for various planning algorithms have been built.

Fig. 6.
figure 6

Graphs of dependence of the OF value (a) and planning time (b) on the number of applications for various planning algorithms

Full size image

The obtained experimental results show that the proposed method is comparable with centralized scheduling methods in terms of the scheduling quality. While with an increase in the number of planned applications, it demonstrates a more linear growth in the processing time without any loss of quality.

6 Conclusion

The authors of the paper proposed a method for adaptive planning of large-scale space observation systems based on multi-agent technologies. Results of experimental studies on the developed prototype demonstrate compliance of the presented approach with requirements for methods and tools of planning large-scale SpOS in terms of scalability, adaptability, flexibility, efficiency, reliability and survivability. As the next step, it is proposed to introduce the concepts of more advanced virtual market and ontology of space observation systems into the multi-agent system to provide the possibility of more flexible and adaptive planning settings. All these actions will ultimately create an actual platform for planning space observation systems.