Data processing: measuring – calibrating – or testing – Measurement system in a specific environment – Earth science
Reexamination Certificate
2000-06-26
2003-09-30
McElheny, Jr., Donald E. (Department: 2857)
Data processing: measuring, calibrating, or testing
Measurement system in a specific environment
Earth science
Reexamination Certificate
active
06629037
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the optimization of infill survey paths for marine seismic surveys, which are designed to uniformly sample subsurface horizons.
2. Related Art
In seismic surveys, much of the subsurface is not properly sampled due to cable feathering. Thus in order to sample those areas that were missed on the first pass, a seismic vessel is required to make additional passes through a prospect survey area, which significantly increases the time and associated cost to complete a survey. These secondary paths are referred to as “infill shooting”. There are an infinite number of possible paths which the vessel may traverse during the infill portion of the survey. Moreover, in many cases, the optimal infill path is difficult to determine. If optimal infill paths can be identified, however, it significantly lowers the total effort and expense associated with seismic data collection. Thus, there is a need for an efficient means of determining optimal infill paths in seismic surveying.
A large portion of marine data collection is devoted to the infill portion of a prospect. The infill may take up to several weeks to complete. Since the typical operating costs of a seismic vessel exceed $50,000 per day, the infill data is very expensive. Thus, optimal infill shooting would result in an enormous cost savings for surveying each seismic prospect. These large cost reductions would provide a competitive advantage in the marine data collection market.
There are many known techniques that have been utilized in an attempt to optimize a given set of data. For example, genetic algorithms, simulated annealing, cellular automata, and calculus-based algorithms have all been used to optimize different physical quantities. Many known procedures have been developed for finding the shortest route between two points. One of the more useful techniques was advanced by Lee. Lee's algorithm is able to find the shortest path between two points on a rectangular grid containing obstacles. In Lee's scheme, movement is restricted to the vertical and horizontal directions. Referring to
FIG. 1
, a shortest path route is developed in the following manner: Starting with a “goal” cell, a “1” is placed in all adjacent empty cells as shown in FIG.
1
. Next, a “2” is placed in any cell which borders a cell containing a value of “1”. This process continues until the “start” cell is reached.
The optimal path is determined by beginning at the “start” cell
100
and moving to the bordering cell
102
with the lowest numeric value. Note that during the path generation phase, diagonal moves are permitted, however, in some cases they may not be allowed. For example, a cab driver must keep his vehicle on paved roads and may not take a diagonal path through private property. The optimal path
103
for the preceding example is shown in FIG.
2
.
Removing one of the object cells
104
, results in multiple path solutions
105
,
106
, however, as shown in FIG.
3
. When equal cost solutions exist, the problem is referred to as a digital indiscrimination problem. Each separate path is referred to as a geodesic. In this example only two equal paths exist. A larger map containing several thousand cells could yield dozens of equivalent geodesics. At first glance, the digital indiscrimination issue may not appear to be problematic, however, in many cases one path may be preferred over another. For example, a straighter path may be favored over one that has several turns.
Moreover, the shortest path does not always mean it is also the least cost path. Consider the problem of a traveling salesman attempting to drive to the airport on the other side of town. The salesman has the choice of taking the long freeway route around town or the shorter drive, straight through the middle of the city. The short route through town might enable the salesman to catch an earlier flight and make additional sales, however, if there are traffic jams in the city, getting stuck in traffic could cause the salesman to miss both flights.
In the traveling salesman example the least cost path depends on the time of day the salesman wants to drive to the airport. In general, determining an optimal route depends on a number of factors. Unlike the shortest path algorithm, the least cost technique requires an initial “cost map”. Cost maps are generated by subdividing a map of an area into an array of cells. A cost value is assigned to each map cell. Cost values typically represent the cost incurred in moving from one map cell to another. For the two dimensional salesman problem, the freeway path would be assigned a low cost value and areas of high traffic density in the city would be assigned a higher cost value. Obstacles such as lakes, rivers, or canyons would be assigned very large cost values. By correctly processing the resulting cost map, the salesman would be able to generate a “best cost map”. This map will enable him to determine the optimal route to the airport.
If all non-object cells in a cost map are equally weighted, the resulting best-cost map is equivalent to a shortest path map. For example, consider the least cost map shown in FIG.
4
. Each entry in the example of
FIG. 4
represents the cost of moving from one cell to another. All cells in the best-cost map are initialized with large integers. To generate a final best cost BC map, we can utilize the Stiles and Glickstein method (see P. N. Stiles and I. S. Glickstein [1994], “Highly Parallelizable Route Planner Bases on Cellular Automata Algorithms.” IBM J. RES. Develop. Vol. 38 No. 2 March 1994, pp. 167-181). The Stiles and Glickstein method begins by setting the goal cell in the BC map equal to zero and adds the map cost of an adjacent cell (MC
j
). The cost for moving to cell BC
j
is therefore calculated as:
cost=
BC
i
+MC
j
where
BC
i
=best cost value for current cell I
MC
j
=map cost of cell adjacent to current cell
The cost for moving to another cell adjacent cell, BC is then calculated. If the resulting cost is less than the BC
j
, the map cost is replaced with the new value, i.e., BC
j
=cost. Since the value for BC
j
has changed, the cell is placed on a “TO DO” list for further processing. The same procedure is followed for all adjacent cells. When all bordering cells have been processed, the cell at the top of the TODO list is then processed in a similar manner. The cells on the TODO list are processed until the TODO list is empty. The pseudo code developed for this process is shown below in table 1 (see, P. N. Stiles, I. S. Glickstein, [1994] pp. 167-181).
TABLE 1
2D serial implementation of Cellular automata algorithm
(P. N. Stiles, L. S. Glickstein, [1994] pp. 167-181).
1.
Initialization
Set all BC
j
= ∞
All Mail Flags MF
j
TODO list is empty
BC
goal
= 0
2.
Cost minimization: loop until TODO list is empty
Cost − BC
j
+ MC
j
If cost < BC
j
BC
j
= cost
If MF
j
= false add j to TODO list and set MF
j
= true
3.
Path generation
First path cell = start cell
Loop until goal cell is reached
Examine BC value of each nearest neighbor
(eight neighbors for 2D)
Select next path cell as cell with lowest BC value
Notation
BC
j
is the I
th
element of best-cost propagation array
(e.g. BC
start
= value of BC at the path start position
MC
1
is the I
th
element of map-cost array MC.
Mfi is the I
th
element of mail-flag array MF, which
Indicates that a cell is on the TODO list
TODO list is a list of cells that can potentially
Update their neighbors
The final BC map is identical to the map shown in FIG.
2
. Now, consider a slightly modified BC map as shown in FIG.
5
. If the least cost algorithm is applied to this BC map, a completely different path
107
is generated, as shown in FIG.
6
. The path is now longer than the path calculated by the shortest route algorithm, however, the travel cost is less.
In the above examples,
Figatner David S.
Madan Mossman & Sriram
McElheny Jr. Donald E.
WesternGeco L.L.C.
LandOfFree
Optimal paths for marine data collection does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Optimal paths for marine data collection, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal paths for marine data collection will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3016639