JP7800666B2 - Imaging planning system and imaging planning method - Google Patents

Description

The present invention relates to an imaging planning system and an imaging planning method, and in particular to an imaging planning system and an imaging planning method that determine the allocation of imaging locations among multiple satellites and the order of imaging.

A plan for a single orbiting satellite (hereinafter simply referred to as a satellite) to image multiple points on Earth is obtained by representing the imaging order of the multiple points as a DAG (Directed Acyclic Graph) and finding the longest path from the DAG. Note that in this specification, "satellite" refers to an artificial satellite.

Figure 15 is an explanatory diagram showing an example of creating an imaging plan using a single satellite. As shown in the left part of Figure 15, in this example, we consider creating a plan for a single orbiting satellite to image imaging points 1 to 5 on Earth.

As shown on the right side of Figure 15, in this example, the imaging order of the orbiting satellite's imaging points 1 to 5 is represented by a DAG. The nodes (circles) that make up the DAG shown in Figure 15 represent imaging points. The edges (arrows) that make up the DAG shown in Figure 15 represent the order in which imaging can be performed. The meanings of each notation are the same in other figures.

Specifically, the edges represent the order in which images can be captured, taking into account the constraints of the orbiting satellites. For example, the DAG shown in Figure 15 indicates that an orbiting satellite can capture image point 1, followed by image point 3 or image point 5.

The DAG shown in Figure 15 also indicates that the orbiting satellite can image imaging point 4 or imaging point 5 after imaging point 2. The DAG shown in Figure 15 also indicates that the orbiting satellite can image imaging point 4 or imaging point 5 after imaging point 3.

In addition, the weight of the nodes that make up the DAG shown in Figure 15 indicates that the node represents a more prioritized imaging location, as the value increases. As shown in Figure 15, the weights of imaging locations 1 to 5 are "1," "2," "2," "1," and "1," respectively.

If the imaging points are imaged in the order that maximizes the total weight set as above, the orbiting satellite can image the greatest number of imaging points. The order that maximizes the total weight, i.e., the longest route in the DAG, is "imaging point 1 → imaging point 3 → imaging point 4."

As shown in Figure 15, when an imaging plan is created using DAG, an imaging plan is created that captures more imaging locations.

Patent document 1 also describes a task communication method that enables the use of a one-to-one synchronous communication API (Application Programming Interface) without causing deadlocks in inter-task synchronous communication in a process consisting of multiple tasks and synchronous communication.

Patent document 2 also describes a method for determining an image layout that includes a step of accessing multiple image elements having an ordered sequence.

Patent document 3 also describes a method for planning the acquisition of images of a ground area by a spacecraft, which is optimal for meeting the local and cumulative constraints of the spacecraft and allows for consideration of ground areas that need to be acquired multiple times or in a single acquisition.

Japanese Patent Application Laid-Open No. 2013-205966 Special Publication No. 2016-524243 Special table 2018-522775 publication

In addition to single satellites, constellations are also used, with multiple satellites taking images at high frequency. However, planning an imaging mission using multiple satellites is a complex and time-consuming task.

For example, when multiple satellites share an imaging location, it is necessary to take into account the fact that even at the same imaging location, imaging times differ depending on the satellite, and that multiple satellites can image in parallel.

Figure 16 is an explanatory diagram showing the challenges involved in planning an imaging plan using multiple satellites. Figure 16 shows a DAG representing the imaging order for satellite 1 and a DAG representing the imaging order for satellite 2.

For example, the two imaging points 1 shown in Figure 16 are imaged by different satellites and at different times. Even if they are the same imaging point, if the satellites that image them and the times that they are imaged are different, they cannot be treated as a single node.

Therefore, the two imaging points 1 shown in Figure 16 are subject to the condition that "only one of them can be imaged." Similarly, the two imaging points 3 shown in Figure 16 are subject to the condition that "only one of them can be imaged."

Furthermore, for example, imaging point 2 shown in Figure 16 and other imaging points can both be imaged even if the imaging time is the same, as long as the satellites taking the images are different. Therefore, imaging point 2 shown in Figure 16 and other imaging points are subject to the condition that "both can be imaged at the same time."

As described above, simply concatenating each DAG representing the imaging order for each satellite does not result in an appropriate DAG that can be used to plan imaging using multiple satellites. Patent documents 1 to 3 do not describe technology for planning imaging using multiple satellites using a DAG.

Furthermore, the mainstream method for improving computer performance is to improve the performance of multiple cores rather than the performance of a single CPU (Central Processing Unit) core. In other words, in order to speed up the development of imaging plans, it is important to make the planning logic easy to parallelize.

Therefore, the present invention aims to provide an imaging planning system and an imaging planning method that can quickly create imaging plans using multiple satellites.

The imaging planning system of the present invention is an imaging planning system that includes a planning unit that plans an imaging plan in which multiple satellites will image multiple imaging locations.The planning unit generates a single DAG by combining DAGs that represent the imaging order in which one satellite will image multiple imaging locations so that predetermined conditions are satisfied across the multiple satellites, performs a topological sort on the single generated DAG, and obtains the longest path in the single DAG that has been topologically sorted.

The imaging planning method of the present invention is an imaging planning method executed in an imaging planning system that plans an imaging plan in which multiple satellites will image multiple imaging locations, and is characterized in that the imaging planning system generates a single DAG by combining DAGs representing the imaging order in which one satellite will image multiple imaging locations so that predetermined conditions are satisfied across the multiple satellites, performs a topological sort on the single generated DAG, and obtains the longest path in the single DAG that has been topologically sorted.

A computer-readable recording medium having recorded thereon an imaging plan development program according to the present invention stores an imaging plan development program that, when executed on a computer, generates a single DAG by combining DAGs representing the imaging order in which one satellite will image multiple imaging locations so that predetermined conditions are satisfied across multiple satellites, performs a topological sort on the single generated DAG, and obtains the longest path in the single DAG that has been topologically sorted, in order to develop an imaging plan in which multiple satellites will image multiple imaging locations.

The present invention enables imaging plans using multiple satellites to be developed quickly.

1 is a block diagram showing an example of the configuration of an imaging planning system according to an embodiment of the present invention. 10 is a flowchart showing the operation of an imaging planning process by the imaging planning system 100 of the present embodiment. 10 is a flowchart showing the operation of a DAG combining process by the imaging plan generation processing unit 110 of this embodiment. 10 is an explanatory diagram showing an example of arranging nodes constituting each DAG in a grid pattern by the imaging plan generation processing unit 110. FIG. 10 is an explanatory diagram showing an example of connecting a node by the imaging plan generation processing unit 110 with a node of another satellite. FIG. FIG. 10 is an explanatory diagram showing another example of connecting a node by the imaging plan generation processing unit 110 with a node of another satellite. 10 is a flowchart showing the operation of a route generation process by an imaging plan generation processing unit 110 of the present embodiment. 10 is an explanatory diagram showing an example of topological sorting performed on a DAG by the imaging plan generation processing unit 110. FIG. 10 is a flowchart showing the operation of a general node score update process. 10 is a flowchart showing the operation of a node score update process by the imaging plan generation processing unit 110 of this embodiment. 10 is a flowchart showing the operation of an imaging order acquisition process performed by an imaging plan generation processing unit 110 of this embodiment. 10 is an explanatory diagram showing an example of deleting a node from the longest route by the imaging plan generation processing unit 110. FIG. 1 is an explanatory diagram showing an example of the hardware configuration of an imaging planning system 100 according to the present invention. 1 is a block diagram showing an overview of an imaging planning system according to the present invention. FIG. 10 is an explanatory diagram showing an example of creating an imaging plan using one satellite. FIG. 1 is an explanatory diagram showing the problems that arise when planning an imaging project using multiple satellites.

[Configuration Description]
[0023] Hereinafter, an embodiment of the present invention will be described with reference to the drawings. Fig. 1 is a block diagram showing an example of the configuration of an imaging planning system according to an embodiment of the present invention. As shown in Fig. 1, an imaging planning system 100 according to this embodiment includes an imaging plan generation processing unit 110.

As mentioned above, when multiple orbiting satellites are tasked with capturing multiple imaging locations without overlapping, it is necessary to consider which satellites will capture which locations and in what order. Furthermore, the number of possible combinations of imaging orders for each satellite is enormous.

The imaging planning system 100 of this embodiment expresses the order in which multiple satellites take images in parallel using a DAG, and by using a method to solve for the longest route that incorporates a mechanism to avoid overlaps, it is possible to quickly create plans for multiple orbiting satellites to share the imaging of multiple imaging locations.

In this embodiment, we consider the case of creating a plan to divide the image capture tasks among multiple orbiting satellites at multiple locations on Earth. As shown in Figure 1, a DAG representing the order in which the images will be captured at multiple locations is prepared as input data for each orbiting satellite.

In this embodiment, the imaging plan generation processing unit 110 combines the DAGs for each prepared orbiting satellite. Next, the imaging plan generation processing unit 110 calculates the longest route and obtains the imaging points and imaging order assigned to each satellite. As shown in Figure 1, the imaging plan generation processing unit 110 outputs data indicating the imaging order of the imaging points for each satellite as output data.

[Operation description]
The operation of the imaging planning system 100 of this embodiment for planning an imaging plan using a plurality of orbiting satellites will be described below with reference to Fig. 2. Fig. 2 is a flowchart showing the operation of the imaging planning process by the imaging planning system 100 of this embodiment.

First, the imaging plan generation processing unit 110 of the imaging plan development system 100 receives multiple input data, each of which indicates a DAG for each satellite (step S110).

Next, the imaging plan generation processing unit 110 performs a DAG combination process to combine the DAGs for each satellite indicated by the multiple input data into one DAG (step S120).

Next, the imaging plan generation processing unit 110 performs a path generation process to find the longest path from the DAG joined in step S120 (step S130).

Next, the imaging plan generation processing unit 110 performs an imaging order acquisition process to determine the imaging order for each satellite from the longest route obtained in step S130 (step S140).

Next, the imaging plan generation processing unit 110 outputs the imaging order for each satellite determined in step S140 (step S150). After outputting the imaging order for each satellite, the imaging plan development system 100 terminates the imaging plan development process.

Next, the DAG joining process of step S120, which is a sub-process constituting the imaging plan creation process shown in Figure 2, will be described with reference to Figure 3. Figure 3 is a flowchart showing the operation of the DAG joining process by the imaging plan generation processing unit 110 of this embodiment.

The imaging plan generation processing unit 110 arranges the nodes that make up each DAG in a grid pattern for each input satellite in order of earliest imaging time (step S121).

Next, the imaging plan generation processing unit 110 connects all of the placed nodes to nodes of other satellites in order of earliest imaging time (step S122). After the connections are complete, the imaging plan generation processing unit 110 returns to the imaging plan formulation process shown in Figure 2.

Figure 4 is an explanatory diagram showing an example of arranging the nodes that make up each DAG in a grid by the imaging plan generation processing unit 110. Figure 4 shows an example of arranging the nodes that make up each DAG of satellites 1 to m by the imaging plan generation processing unit 110 in step S121.

4, the imaging plan generation processing unit 110 arranges each node constituting the DAG in the order of imaging times _t1 to _tn from the top. In addition, the imaging plan generation processing unit 110 arranges multiple nodes with the same imaging time in a horizontal row. The imaging plan generation processing unit 110 performs the above-mentioned arrangement processing for each DAG.

Figure 5 is an explanatory diagram showing an example of connecting nodes by the imaging plan generation processing unit 110 to nodes of other satellites. Figure 5 shows an example of connecting the nodes that make up each DAG of satellite 1 and satellite 2 by the imaging plan generation processing unit 110 in step S122.

When connecting a node, the imaging plan generation processing unit 110 selects as the connection destination a node of another satellite whose imaging time is the same as the imaging time of the connection source node, or a node whose imaging time is in the future. As indicated by the dashed arrow in Figure 5, the imaging plan generation processing unit 110 does not select as the connection destination a node whose imaging time is earlier than the imaging time of the connection source node.

As shown in Figure 5, when connecting to a destination node with the same imaging time, the imaging plan generation processing unit 110 copies the destination node and output edge (only edges that output to nodes on the same satellite). Next, the imaging plan generation processing unit 110 connects the source node, the copied destination node, and the copied output edge.

Also, as shown in Figure 5, when connecting to a destination node whose imaging time is in the future, the imaging plan generation processing unit 110 directly connects the source node and the destination node.

When connections are made as shown in Figure 5, no closed loops are generated. In other words, the imaging plan generation processing unit 110 can represent the order in which multiple satellites take images in parallel as a DAG.

Note that Figure 5 shows an example in which the imaging plan generation processing unit 110 connects from the nodes that make up the DAG of satellite 1 to the nodes that make up the DAG of satellite 2. However, the imaging plan generation processing unit 110 can also connect in the opposite direction, i.e., from the nodes that make up the DAG of satellite 2 to the nodes that make up the DAG of satellite 1.

Figure 6 is an explanatory diagram showing another example of connecting a node by the imaging plan generation processing unit 110 to a node of another satellite.

As shown in Figure 6, if there are multiple columns of nodes that make up a DAG in which the nodes are arranged in a grid pattern on the destination satellite, the imaging plan generation processing unit 110 selects a destination node for each column and performs a connection operation.

For example, the imaging plan generation processing unit 110 connects the nodes that make up the DAG of satellite 1 to the nodes in column 1 and column 2 that make up the DAG of satellite 2. Note that the way in which the imaging plan generation processing unit 110 connects the nodes shown in Figure 6 is the same as the way in which the imaging plan generation processing unit 110 connects the nodes shown in Figure 5.

Next, the route generation process of step S130, which is a sub-process constituting the imaging plan formulation process shown in Figure 2, will be described with reference to Figure 7. Figure 7 is a flowchart showing the operation of the route generation process by the imaging plan generation processing unit 110 of this embodiment.

The imaging plan generation processing unit 110 combines the multiple start nodes and multiple end nodes in the single DAG generated in step S120 into one. After combining, the imaging plan generation processing unit 110 performs a topological sort on the single generated DAG (step S131).

Next, the imaging plan generation processing unit 110 updates the node scores to the maximum value in the topologically sorted order, from the grouped start node to the grouped end node (step S132).

Next, the imaging plan generation processing unit 110 generates the longest path by tracing the input source nodes recorded in the nodes from the grouped end nodes to the grouped start nodes (step S133).

After generating the longest path, the imaging plan generation processing unit 110 returns to the imaging plan formulation process shown in Figure 2. The method of finding the longest path after topologically sorting the DAG shown in Figure 7 is a common method of finding the longest path from a DAG.

Figure 8 is an explanatory diagram showing an example of topological sorting performed on a DAG by the imaging plan generation processing unit 110. Figure 8 shows an example of topological sorting performed by the imaging plan generation processing unit 110 in step S131. Note that Figure 8 shows some of the nodes and edges that make up the DAG.

As shown in the left part of Figure 8, the imaging plan generation processing unit 110 combines multiple start nodes and multiple end nodes in one DAG generated in step S120 into one. The two rounded rectangles shown in Figure 8 represent the combined start node and the combined end node, respectively.

After combining multiple start nodes and multiple end nodes into one, the imaging plan generation processing unit 110 performs a topological sort on the DAG. The right part of Figure 8 shows the DAG after topological sorting.

Regarding the processing of step S132, the imaging plan generation processing unit 110 generally calculates the node score as "the score of the input source node + the weight of the input source node."

The operation of updating the scores of nodes constituting a general DAG to the maximum value will be explained below with reference to Figure 9. Figure 9 is a flowchart showing the operation of a general node score update process. For ease of explanation, the imaging plan generation processing unit 110 is the subject of each process shown in Figure 9.

The imaging plan generation processing unit 110 initializes the scores of all nodes that make up the DAG to 0 (step S001). Next, the imaging plan generation processing unit 110 enters a node loop (step S002).

The imaging plan generation processing unit 110, which has entered the node loop, extracts one node whose score has not yet been updated from the topologically sorted DAG. In other words, the imaging plan generation processing unit 110 enters the edge loop (step S003).

When the imaging plan generation processing unit 110 enters the edge loop, it extracts one of the input edges to the extracted node that has not yet been processed.

The input edge has a source node recorded. The imaging plan generation processing unit 110 determines whether the score of the extracted node is less than the sum of the "source node score" and "source node weight" recorded in the extracted input edge (step S004).

If the node score is greater than or equal to the sum of the "score of the input source node" and the "weight of the input source node" (False in step S004), the imaging plan generation processing unit 110 returns to the processing of step S003 and processes the next input edge.

If the node score is smaller than the sum of the "score of the input source node" and the "weight of the input source node" (True in step S004), the imaging plan generation processing unit 110 updates the node score to "score of the input source node + weight of the input source node" (step S005).

Next, the imaging plan generation processing unit 110 updates the input source node to the extracted node to the input source node recorded in the extracted input edge (step S006). After updating, the imaging plan generation processing unit 110 returns to the processing of step S003 and processes the next input edge.

The imaging plan generation processing unit 110 repeatedly executes steps S004 to S006 until all input edges to the extracted node have been processed. When all input edges to the extracted node have been processed, the imaging plan generation processing unit 110 exits the edge loop (step S007).

The imaging plan generation processing unit 110 repeatedly performs steps S003 to S007 in the order of the topologically sorted nodes until the scores of all the topologically sorted nodes have been updated.

When the scores of all topologically sorted nodes have been updated, the imaging plan generation processing unit 110 exits the node loop (step S008). Upon exiting the node loop, the imaging plan generation processing unit 110 terminates the node score update process.

In this embodiment, the general node score update process shown in Figure 9 is modified as shown in Figure 10. Below, the operation of the imaging plan generation processing unit 110 of this embodiment to update the scores of the nodes that make up the DAG to the maximum value will be described with reference to Figure 10. Figure 10 is a flowchart showing the operation of the node score update process by the imaging plan generation processing unit 110 of this embodiment.

The imaging plan generation processing unit 110 initializes the scores of all nodes that make up the DAG to 0 (step S901). Next, the imaging plan generation processing unit 110 enters a node loop (step S902).

The imaging plan generation processing unit 110, which has entered the node loop, extracts one node whose score has not yet been updated from the topologically sorted DAG. In other words, the imaging plan generation processing unit 110 enters the edge loop (step S903).

When the imaging plan generation processing unit 110 enters the edge loop, it extracts one of the input edges to the extracted node that has not yet been processed.

The input edge records the source node. The imaging plan generation processing unit 110 determines whether the satellite imaging the extracted node is different from the satellite imaging the source node recorded in the extracted input edge (step S904). For convenience, the "satellite imaging the node" is referred to as the "satellite of the node" in Figure 10.

If the satellite imaging the extracted node is different from the satellite imaging the input source node recorded in the extracted input edge (True in step S904), the imaging plan generation processing unit 110 sequentially traces the input source nodes of the input source node recorded in the extracted input edge. By sequentially tracing the input source nodes, the imaging plan generation processing unit 110 searches for nodes imaged by the same satellite as the satellite imaging the extracted node (step S905).

If no nodes imaged by the same satellite are found (No in step S906), the imaging plan generation processing unit 110 proceeds to processing in step S908.

If a node imaged by the same satellite is found (Yes in step S906), the imaging plan generation processing unit 110 determines whether the node from which the satellite was extracted after the found node cannot be imaged (step S907).

If the satellite cannot image the extracted node (Yes in step S907), the imaging plan generation processing unit 110 returns to the processing of step S903 and processes the next input edge.

If the satellite can image the extracted node (No in step S907), the imaging plan generation processing unit 110 proceeds to processing in step S908.

If the satellite imaging the extracted node is the same as the satellite imaging the input source node recorded in the extracted input edge (False in step S904), the imaging plan generation processing unit 110 initializes the variable weight to 0 (step S908).

Next, the imaging plan generation processing unit 110 sequentially traces the input source nodes of the input source nodes recorded in the extracted input edge. By tracing the input source nodes sequentially, the imaging plan generation processing unit 110 searches for a node indicating the same imaging location as the imaging location indicated by the extracted node (step S909).

If a node indicating the same imaging location is not found (No in step S910), the imaging plan generation processing unit 110 proceeds to processing in step S912.

If a node indicating the same imaging location is found (Yes in step S910), the imaging plan generation processing unit 110 sets the weight of the node indicating the same imaging location found to the variable weight (step S911).

Next, the imaging plan generation processing unit 110 determines whether the score of the extracted node is less than the difference between the sum of the "score of the input source node" and the "weight of the input source node" recorded in the extracted input edge and the variable weight (step S912).

If the node score is greater than or equal to the difference between the sum of the "score of the input source node" and the "weight of the input source node" and the variable weight (False in step S912), the imaging plan generation processing unit 110 returns to the processing of step S903 and processes the next input edge.

If the node score is smaller than the difference between the sum of the "score of the input source node" and the "weight of the input source node" and the variable weight (True in step S912), the imaging plan generation processing unit 110 updates the node score to "score of the input source node + weight of the input source node - variable weight" (step S913).

Next, the imaging plan generation processing unit 110 updates the input source node to the extracted node to the input source node recorded in the extracted input edge (step S914). After updating, the imaging plan generation processing unit 110 returns to the processing of step S903 and processes the next input edge.

The imaging plan generation processing unit 110 repeatedly executes steps S904 to S914 until all input edges to the extracted node have been processed. When all input edges to the extracted node have been processed, the imaging plan generation processing unit 110 exits the edge loop (step S915).

The imaging plan generation processing unit 110 repeatedly performs steps S903 to S915 in the order of the topologically sorted nodes until the scores of all the topologically sorted nodes have been updated.

When the scores of all topologically sorted nodes have been updated, the imaging plan generation processing unit 110 exits the node loop (step S916). Upon exiting the node loop, the imaging plan generation processing unit 110 terminates the node score update process.

In this embodiment, the imaging plan generation processing unit 110 updates the node score and the input source node of the node by executing the node score update process shown in Figure 10 in step S132. Once the node score and the input source node of the node are updated as shown in Figure 10, the imaging plan generation processing unit 110 can determine the longest path from the DAG in step S133.

Also, as mentioned above, the processing of steps S004 to S006 shown in Figure 9 has been changed to the processing of steps S904 to S914 shown in Figure 10. The above changes are made to satisfy the conditions shown in Figure 16, "only one of the two can be photographed" and "both can be photographed at the same time."

Next, the imaging order acquisition process of step S140, which is a sub-process constituting the imaging plan creation process shown in Figure 2, will be described with reference to Figure 11. Figure 11 is a flowchart showing the operation of the imaging order acquisition process by the imaging plan generation processing unit 110 of this embodiment.

The imaging plan generation processing unit 110 traces the longest path found in step S130 from the end node to the start node. If a node indicating an imaging location that has already been detected during the tracing, the imaging plan generation processing unit 110 deletes the detected node (step S141).

Next, the imaging plan generation processing unit 110 classifies the nodes remaining on the longest route by satellite. Next, the imaging plan generation processing unit 110 arranges the nodes classified by satellite in order of earliest imaging time (step S142).

By classifying the remaining nodes by satellite and arranging them in order of earliest imaging time, the imaging plan generation processing unit 110 can determine the imaging order for each satellite. After determining the imaging order for each satellite, the imaging plan generation processing unit 110 returns to the imaging plan formulation processing shown in Figure 2.

Figure 12 is an explanatory diagram showing an example of deleting a node from the longest path by the imaging plan generation processing unit 110. Figure 12 shows an example of deleting a duplicate node by the imaging plan generation processing unit 110 in step S141.

In the longest route shown in the left part of Figure 12, the two circles marked "1" represent two nodes that indicate the same imaging location. If the imaging plan generation processing unit 110 detects a node that indicates a previously mentioned imaging location while tracing the longest route from the end node to the start node, it deletes the second circle marked "1," as shown in the right part of Figure 12.

As described above, the imaging planning system 100 of this embodiment is an imaging planning system that includes an imaging plan generation processing unit 110 that plans an imaging plan in which multiple satellites image multiple imaging locations.

The imaging plan generation processing unit 110 generates a single DAG by combining DAGs representing the imaging order in which a single satellite will image multiple imaging locations so that a predetermined condition is met across multiple satellites, performs a topological sort on the single DAG generated, and obtains the longest path in the single DAG that has undergone topological sorting. The predetermined condition is that no closed paths are generated.

The imaging plan generation processing unit 110 also classifies the multiple imaging points that make up the acquired longest route by the satellite that captures the images, and creates an imaging plan by executing a process for each satellite to arrange the classified multiple imaging points in order of imaging time. Furthermore, the imaging plan generation processing unit 110 deletes the imaging point with the earlier imaging time from among the overlapping imaging points on the acquired longest route.

In addition, the imaging plan generation processing unit 110 calculates the score of the node that indicates the imaging location and the input source node of the node for each of all nodes that constitute a single DAG after topological sorting.

In addition, the imaging plan generation processing unit 110 calculates the node score and the input source node of the node so that the condition that only one of multiple nodes indicating the same imaging location can be imaged is satisfied.

In addition, the imaging plan generation processing unit 110 calculates the node score and the input source node of the node so that the condition that multiple nodes indicating different imaging locations can all be imaged at the same imaging time is met.

Furthermore, a DAG representing the imaging sequence of a single satellite may have multiple columns in which multiple imaging locations are arranged in order of imaging time.

The imaging plan generation processing unit 110 of this embodiment may replace the DAG for each satellite with a DAG for each path. By doing so, the imaging plan generation processing unit 110 can plan which path to use to image an imaging location that can be imaged by a single satellite from either of two paths. The imaging plan generation processing unit 110 of this embodiment can also create imaging plans for multiple satellites that can be imaged from either of multiple paths.

[Effect description]
When the imaging plan generation processing unit 110 of this embodiment combines multiple DAGs that represent the imaging order when imaging is performed by a single satellite, it selects and copies the destination nodes so that a closed loop is not created, thereby maintaining the combined graph as a DAG.

The imaging plan generation processing unit 110 also performs a topological sort on the combined DAG to find the longest path. When finding the longest path, the imaging plan generation processing unit 110 calculates a score taking into account overlapping imaging points.

The imaging plan generation processing unit 110 then removes overlapping points from the longest route. The imaging plan generation processing unit 110 then classifies the remaining imaging points on the longest route by satellite and obtains the imaging order for the imaging points assigned to each satellite.

Therefore, the imaging planning system 100 of this embodiment obtains the allocation of imaging locations and imaging order for multiple satellites by finding the longest path from the DAG. When topological sorting is performed, the longest path can be quickly obtained from the DAG. In other words, the imaging planning system 100 can quickly create imaging plans for multiple satellites.

The imaging plan creation system 100 of this embodiment can be easily implemented using a programming language with simple logic. Furthermore, since many parts of the processing by the imaging plan generation processing unit 110 can be executed in parallel, when the imaging plan generation processing unit 110 is controlled by a many-core CPU, the imaging plan generation processing unit 110 can execute processing at higher speeds.

Of the processes performed by the imaging plan generation processing unit 110, steps S121, S122, and S903 can be executed in parallel. The process of step S121 can be executed in parallel for each satellite. The process of step S122 can be executed in parallel for each node. Each process within the loop of step S903 can be executed in parallel. Because the processes performed by the imaging plan generation processing unit 110 can easily be executed in parallel, they can be easily accelerated.

The present invention may be used in the fields of Earth observation or drone aerial photography.

Below, we will explain a specific example of the hardware configuration of the imaging planning system 100 of this embodiment. Figure 13 is an explanatory diagram showing an example of the hardware configuration of the imaging planning system 100 according to the present invention.

The imaging planning system 100 shown in Figure 13 includes a CPU 11, a main memory unit 12, a communication unit 13, and an auxiliary memory unit 14. It also includes an input unit 15 for user operation and an output unit 16 for presenting the processing results or the progress of the processing content to the user.

The imaging planning system 100 is realized by software, with the CPU 11 shown in Figure 13 executing a program that provides the functions of each component.

In other words, the CPU 11 loads and executes the program stored in the auxiliary memory unit 14 into the main memory unit 12, and controls the operation of the imaging planning system 100, thereby realizing each function through software.

The imaging planning system 100 shown in FIG. 13 may include a DSP (Digital Signal Processor) instead of the CPU 11. Alternatively, the imaging planning system 100 shown in FIG. 13 may include both the CPU 11 and a DSP.

The main memory unit 12 is used as a data working area and a data temporary storage area. The main memory unit 12 is, for example, RAM (Random Access Memory).

The communication unit 13 has the function of inputting and outputting data between peripheral devices via a wired network or a wireless network (information and communication network).

The auxiliary memory unit 14 is a non-transitory tangible storage medium. Examples of non-transitory tangible storage media include magnetic disks, magneto-optical disks, CD-ROMs (Compact Disk Read Only Memory), DVD-ROMs (Digital Versatile Disk Read Only Memory), and semiconductor memories.

The input unit 15 has the function of inputting data and processing commands. The input unit 15 is an input device such as a keyboard, mouse, or touch panel.

The output unit 16 has the function of outputting data. The output unit 16 is, for example, a display device such as an LCD device, a touch panel, or a printing device such as a printer.

Also, as shown in FIG. 13, in the imaging planning system 100, each component is connected to a system bus 17.

In the imaging planning system 100, the auxiliary memory unit 14 stores a program for realizing the imaging plan generation processing unit 110.

In addition, the imaging planning system 100 may be implemented with a circuit that includes hardware components such as an LSI (Large Scale Integration) that realizes the functions shown in Figure 1.

The imaging planning system 100 may also be realized by hardware that does not include computer functions using elements such as a CPU. For example, some or all of the components may be realized by general-purpose circuits, dedicated circuits, processors, etc., or a combination of these. These may be configured by a single chip (e.g., the above-mentioned LSI), or by multiple chips connected via a bus. Some or all of the components may be realized by a combination of the above-mentioned circuits, etc., and a program.

In addition, some or all of the components of the imaging planning system 100 may be composed of one or more information processing devices equipped with a calculation unit and a memory unit.

When some or all of the components are realized by multiple information processing devices, circuits, etc., the multiple information processing devices, circuits, etc. may be centrally or decentralized. For example, the information processing devices, circuits, etc. may be realized as a client-server system, cloud computing system, etc., in which each device is connected via a communications network.

Next, an overview of the present invention will be described. Figure 14 is a block diagram showing an overview of an imaging planning system according to the present invention. The imaging planning system 20 according to the present invention is an imaging planning system including a planning unit 21 (e.g., an imaging plan generation processing unit 110) that plans an imaging plan in which multiple satellites will image multiple imaging locations. The planning unit 21 generates a single DAG by combining DAGs representing the imaging order in which one satellite will image multiple imaging locations so that predetermined conditions are satisfied across the multiple satellites, performs a topological sort on the single generated DAG, and obtains the longest path in the single DAG after the topological sorting.

The planning unit 21 may also classify the multiple imaging points that make up the acquired longest route by the satellite that captures the images, and then perform a process for each satellite to arrange the classified multiple imaging points in order of image capture time, thereby creating an imaging plan. The planning unit 21 may also delete the imaging point with the earlier image capture time from among the overlapping imaging points on the acquired longest route.

With such a configuration, the imaging planning system can quickly create imaging plans using multiple satellites.

The specified condition may also be that no closed path is generated.

Such a configuration allows the imaging planning system to maintain the combined graph in a DAG.

The planning unit 21 may also calculate the score of a node that constitutes a single DAG for which topological sorting has been performed and indicates an imaging location, and the input source node of the node, for each of all nodes that constitute a single DAG.

Such a configuration allows the imaging planning system to find the longest path from the DAG in a general way.

The planning unit 21 may also calculate the node score and the input source node of the node so that the condition that only one of multiple nodes indicating the same imaging location can be imaged is satisfied.

The planning unit 21 may also calculate the node score and the node's input source node so that the condition is met that multiple nodes indicating different imaging locations can all be imaged at the same imaging time.

With such a configuration, the imaging planning system can solve the problems associated with planning imaging using multiple satellites.

Furthermore, a DAG representing the imaging sequence of a single satellite may have multiple columns in which multiple imaging locations are arranged in order of imaging time.

The present invention has been described above with reference to the embodiments, but the present invention is not limited to the above embodiments. Various modifications that would be understood by a person skilled in the art can be made to the configuration and details of the present invention within the scope of the present invention.

This application claims priority based on Japanese Patent Application No. 2022-070489, filed on April 22, 2022, the entire disclosure of which is incorporated herein by reference.

11 CPU
12 Main memory unit 13 Communication unit 14 Auxiliary memory unit 15 Input unit 16 Output unit 17 System bus 20, 100 Imaging plan planning system 21 Planning unit 110 Imaging plan generation processing unit

Claims (10)

An imaging plan planning system including a planning unit that plans an imaging plan in which a plurality of satellites capture images of a plurality of imaging points,
The planning unit
generating a Directed Acyclic Graph (DAG) by connecting DAGs representing an imaging order in which one satellite images the plurality of imaging points so that a predetermined condition is satisfied across the plurality of satellites;
A topological sort is performed on the generated DAG.
and acquiring the longest path in the one DAG that has been topologically sorted. The Planning Department
The plurality of imaging points constituting the acquired longest route are classified by the satellites that image them;
2. The imaging plan making system according to claim 1, wherein an imaging plan is made by executing a process of arranging the classified imaging points in order of imaging time for each artificial satellite. The imaging plan making system according to claim 2 , wherein the planning unit deletes an imaging point having an earlier imaging time from among overlapping imaging points on the acquired longest route. The imaging planning system according to claim 1 , wherein the predetermined condition is that no closed path is generated. The imaging planning system according to claim 1, wherein the planning unit calculates the score of a node that constitutes one DAG after topological sorting and indicates an imaging location, and an input source node of the node, for each of all nodes that constitute the one DAG. The imaging plan making system according to claim 5 , wherein the planning unit calculates the score of the node and the input source node of the node so that a condition that only one of a plurality of nodes indicating the same imaging point can be imaged is satisfied. The imaging plan making system according to claim 5 , wherein the planning unit calculates the scores of the nodes and the input source nodes of the nodes so that a condition is satisfied that a plurality of nodes indicating different imaging points can all be imaged at the same imaging time. 2. The imaging planning system according to claim 1, wherein the DAG representing the imaging sequence of one satellite has a plurality of columns in which a plurality of imaging points are arranged in order of imaging time. An imaging plan formulation method executed in an imaging plan formulation system that formulates an imaging plan in which a plurality of satellites image a plurality of imaging points, comprising:
The imaging planning system includes:
generating one DAG by combining DAGs representing an imaging order in which one satellite images the plurality of imaging points so that a predetermined condition is satisfied across the plurality of satellites;
A topological sort is performed on the generated DAG.
and acquiring the longest path in the one DAG that has been topologically sorted. On the computer,
In order to create an imaging plan in which a plurality of satellites image a plurality of imaging points, a DAG is generated by combining DAGs representing an imaging order in which one satellite images the plurality of imaging points so that a predetermined condition is satisfied across the plurality of satellites;
A topological sort is performed on the generated DAG.
Obtain the longest path in the topologically sorted DAG.
A photography planning program for this purpose .