Data processing: artificial intelligence – Knowledge processing system
Reexamination Certificate
1998-03-05
2002-06-11
Powell, Mark (Department: 2122)
Data processing: artificial intelligence
Knowledge processing system
C706S046000, C706S047000, C706S048000
Reexamination Certificate
active
06405186
ABSTRACT:
The present invention relates to a method of planning the various picture-taking requests made of an observation satellite fitted with various sensors (radar, infrared, or optical).
BACKGROUND OF THE INVENTION
A picture-taking request is a particular request coming from a particular customer concerning a particular observation (i.e. a shot of a determined region of the earth).
In general, observation satellites are non-sysnchronous, i.e. their orbital period is such that a particular region of the earth can be observed by a particular satellite at several different instants. The term “opportunity” is used below to designate each possible instant available to a satellite for complying with a given request.
A request may consist in taking a plurality of shots of the same region, e.g. in order to construct a stereoscopic view. It then becomes necessary to provide a plurality of opportunities for the same request in order to satisfy it. A request is said to be “saturated in opportunities” when all of the requested shots have been planned.
In addition, there exist certain constraints that make certain opportunities unsuitable.
Generally, a client making a precise request will specify a limit date before which the client desires the request to be implemented. As a result, the number of opportunities for any given request is limited.
Similarly, it may be known a priori that certain opportunities will be impossible because of bad weather conditions. This constraint applies only to optical sensors.
In addition, a satellite may have requests corresponding to making observations of regions of the earth that are very close together. Because of the limited number of on-board sensors, the satellite may not necessarily be capable of processing all of the observations. Consequently, some of the requests will need to be processed at a later time when the satellite is again passing over the zone in question. In other words, selecting a particular opportunity for one request denies opportunities for other requests.
Also, the satellite must send the images it has taken to ground stations by telemetry. Communication between the satellite and the station is possible only during a short “visibility” period. In addition, communication takes place at a limited data rate, such that the satellite must have a memory that acts as a buffer for storing data before it is transmitted. Since the weight of a satellite is a major design constraint, the amount of memory is limited, and consequently certain request opportunities become impossible to satisfy because of insufficient memory availability.
An additional constraint may be that of communicating the data that results from a request only to a station that is situated in the territory of the country that has made the request. Certain requests can be of a confidential nature (e.g. observations of military sites) and must be retransmitted only to sites approved by the person making the request.
Another constraint can also be that of sharing requests as a function of the client and of the financial contribution that the client has invested in the satellite. The proportion of requests fulfilled per nation must correspond approximately to the proportions of the financial contributions made by those nations.
The planning problem which the present invention seeks to solve is that of scheduling the various requests so as to optimize a given evaluation criterion (planned number of requests, total area corresponding to planned requests, total volume corresponding to planned requests, . . . ) while taking account of the various constraints.
In general, such a planning problem is a part of the class of problems known as “NP-complete”. For a full discussion of NP-complete problems, the reader may refer to the work “Intelligence artificielle et informatique théorique” [Artificial intelligence and theoretical computing] by Jean-Marc Alliot and Thomas Schiex, published by Cépaduès Editions, and more particularly Chapter 11 thereof dealing with complexity theory, or to the English language work “Computers and intractability: a guide to the theory of NP-completeness” by Garey and Johnson published by Freeman, 1979.
It is important to observe that a problem of this type is of complexity which increases in non-polynomial manner with increasing size of problem, i.e. in the present case with increasing number of opportunities to be planned.
Consequently, the problem becomes one of finding a good solution and not necessarily the best solution.
There is no point in making an exhaustive list of the very numerous methods that seek to solve problems of this kind. Nevertheless, by way of example, mention can be made of approaches of the “constraint propagation” type which have been applied to planning observation satellite requests. By way of example, the reader may refer to the article “Exact and approximate methods for the daily management of an earth observation satellite” by J. C. Agnèse, N. Bataille, D. Blumstein, E. Bensana and G. Verfaillie published in a “Artificial Intelligence and Knowledge Based Systems for Space—5th Workshop”, by the European Space Agency.
Mention may also be made of the particular case of the SPOT observation satellite, where planning is performed by an expert system.
Nevertheless, those various solutions do not give very good plans (i.e. the number of planned requests is not very high) and above all they require enormous amounts of computation time before giving an acceptable plan. For example, an implementation of a constraint propagation tape method takes several hours of computation to produce a plan that implements about 70% of the requests in a set of 10,000 requests and 200,000 opportunities.
OBJECT AND SUMMARY OF THE INVENTION
The object of the present invention is to propose a method which gives a request plan that is of better quality than known plans and to do so in a shorter length of time. Typically, for the same example as that mentioned above, the method of the invention gives a plan that satisfies about 80% of the requests and it does so in only a few minutes on a computer of conventional type.
In addition, insofar as the method of the invention is fast enough, it becomes possible to generate plans up to a horizon of several months, which has the particular advantage of improving plan quality.
The method of the invention is an iterative method in which each iteration k is made up of the following steps:
selecting a new opportunity;
drawing up a provisional plan from the plan k-
1
calculated at the preceding iteration and from said new opportunity;
verifying that said provisional plan satisfies the constraints;
evaluating the quality of said provisional plan; and
determining whether the provisional plan should be accepted as the plan k as a function of the quality of said provisional plan and the quality of said plan k-
1
calculated at the preceding iteration;
wherein said provisional plan is confirmed or not by performing a probabilistic metaheuristic of the simulated annealing type.
As with any iterative method, it is important to specify the initial condition of the method and also the stop condition(s).
The initial plan is preferably an empty plan, but it is also possible to precalculate a non-empty initial plan prior to applying the above-mentioned algorithm thereto.
The stop conditions of the algorithm are constituted by conditions that are conventional for this type of iterative algorithm, such as computation time, number of iterations, or the absolute value of the difference in quality between the plan at iteration k and the plan at iteration k-
1
dropping below a certain threshold, for example.
It is also possible to add conditions specific to simulated annealing, such as the temperature dropping beneath a certain threshold (different from the first threshold), for example. The notion of “temperature” is explained below.
Naturally, it is also possible to use other stop conditions or to combine a plurality of stop conditions, while still remaining within the ambit of the present invention.
REFERENCES:
patent: 5623413
Berger Marie
Fabre Benoît
Noreils Fabrice
Alcatel
Powell Mark
Starks Wilbert
Sughrue Mion Zinn Macpeak & Seas, PLLC
LandOfFree
Method of planning satellite requests by constrained... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of planning satellite requests by constrained..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of planning satellite requests by constrained... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2976494