Patent Description:
Mining operations, and in particular surface mining operations, increasingly rely on the analysis of data streams transmitted by various types of mining equipment and vehicles in order to increase productivity and reduce costs. One such data stream may comprise information and data relating to the position and movement of the mining equipment and vehicles within the mining environment. Such position data are commonly obtained from satellite-based position location systems, such as the GPS, Galileo, and GLONASS systems, operatively associated with the mining equipment. Alternatively, the position data maybe obtained or derived from other types of position sensing systems, such as inertial-based systems or ground-based radio navigation systems.

Regardless of the particular type of position sensing system that is used, the resulting position data are subsequently transmitted to a processing system for analysis. In a typical example, the position data may be used by the processing system for fleet tracking and dispatch purposes, thereby allowing for the more efficient deployment and movement of the equipment and vehicles within the mining environment. However, other types of data analysis systems are known, and still others being developed, that rely at least in part on such position data.

One problem associated with systems that use vehicle position data relates to the problem of correlating or matching the measured position data with terrestrial features. In a mining environment, such terrestrial features may involve the road network being traveled by the vehicles. Such terrestrial features may also include other aspects of the mining environment and infrastructure system as well, such as the locations of various service buildings, fueling stations, loading locations, and dump locations, just to name a few.

The difficulties associated with correlating the measured position data with terrestrial features are due in part to inherent uncertainties and errors associated with the vehicle position location system (e.g., GPS). These uncertainties and errors may be compounded by the nature of the mining environment itself. For example, many mining environments are situated in mountainous areas which may adversely impact the accuracy of satellite-based position data. The presence of mountainous terrain may also cause the position data to include a large number of completely erroneous position fixes or 'outliers' that are located a significant distance from the actual position of the vehicle.

Besides difficulties associated with obtaining accurate position measurements, still other difficulties are associated with the configuration of the terrestrial features in the mining environment. For example, the road network in an open pit mine often contains sections of roads that are located in close proximity to one another, on closely parallel paths, and may involve comparatively complex intersections, all of which can create difficulties in properly correlating or matching the measured position of the vehicle with the correct road or location.

Still other problems are created by the dynamic nature of the mining environment itself. For example, the road network and infrastructure system are not static and are frequently changed and reconfigured as the mining operation progresses. Various roads comprising the road network are frequently moved and relocated. Similarly, elements of the mining infrastructure, e.g., service buildings, fueling stations, loading locations, and dump locations, also may be moved from time-to-time. Therefore, besides having to accurately correlate position data with known terrestrial features, a position correlation system must also be capable of accurately correlating the position data with new or relocated terrestrial features, often on a daily basis.

The failure to accurately correlate the positions of the vehicles with such terrestrial features can significantly impact the value of systems that rely on accurate position location and placement of the vehicles. For example, and in the context of a fleet tracking and dispatching system, locating a haul truck on the incorrect road can lead to incorrect dispatch decisions and/or lead to congestion problems if other vehicles are deployed on roads thought to be free of vehicles. Besides limiting the ability of fleet tracking and dispatching systems be used with optimal effectiveness, the difficulties associated with accurately correlating vehicle positions with terrestrial features limits the ability of mining operators to develop new analytical systems and tools to further improve productivity and reduce costs.

<CIT> discloses systems and methods of correlating satellite position data with terrestrial features that may involve: using a geometric snapping algorithm to correlate the satellite position data and terrestrial survey data and snap the satellite position data to the terrestrial features; determining whether the satellite position data can be snapped to unique terrestrial features; and using a hybrid space-time snapping algorithm to correlate the satellite position data and terrestrial survey data and snap the satellite position data to unique terrestrial features when the satellite position data cannot be snapped to unique terrestrial features.

Illustrative and presently preferred exemplary embodiments ntiein are shown in the drawings in which:.

Aspects or embodiments that do not fall under the scope of the claims are useful to understand the invention.

A position correlation system <NUM> according to one embodiment of the present invention is shown and described herein as it could be used to correlate sensed position data <NUM> with terrestrial features <NUM> located within a defined operational area <NUM>. See <FIG> and <FIG>. The defined operational area <NUM> may comprise a surface mine <NUM> or at least a portion of the surface mine <NUM>. The sensed position data <NUM> may be derived from one or more moveable objects <NUM>, such as various types of mining equipment and vehicles, operating within the surface mine <NUM>. The terrestrial features <NUM> may comprise a road network <NUM> defined by a plurality of roads <NUM>. The terrestrial features <NUM> may also comprise other aspects of the mining infrastructure system <NUM>, including, for example, the locations of various service buildings, fueling stations, loading locations, dump locations, and the like. Data regarding the locations of such terrestrial features <NUM> comprise terrestrial data <NUM>. The terrestrial data <NUM> may include any of a wide range of other information and data about the terrestrial features <NUM>, some of which will be described in further detail herein and others of which will become apparent to persons having ordinary skill in the art after having become familiar with the teachings provided herein.

With reference now primarily to <FIG>, the position correlation system <NUM> may comprise a computer processor or computer processing system <NUM> that may be operatively connected to a terrestrial database <NUM> and, optionally, to a position database <NUM>. The terrestrial database <NUM> may comprise terrestrial data <NUM>. Terrestrial data <NUM> may comprise a plurality of records or data files that identify the locations of the various terrestrial features <NUM>, e.g., the various roads <NUM> of road network <NUM> as well as elements of the mining infrastructure system <NUM>, as already described. In addition to location information, terrestrial data <NUM> may also include additional information about the various terrestrial features <NUM>. The position database <NUM> may comprise sensed position data <NUM> obtained from position sensing systems (not shown) operatively associated with the moveable objects <NUM>. The sensed position data <NUM> may comprise a plurality of records or data files that identify the location of one or more moveable objects <NUM> operating within the defined operational area <NUM>. Sensed position data <NUM> may also include other information about the moveable objects or vehicles <NUM> such as, for example, the heading of the vehicle <NUM>.

The sensed position data <NUM> may be collected over time (i.e., may comprise temporal or time-based position data), in which individual sensed locations or position fixes <NUM> (best seen in <FIG>) of the moveable object or vehicle <NUM> are obtained at discrete times. Accordingly, a suitable time stamp may be associated with each individual sensed position point or position fix <NUM> comprising the sensed position data <NUM>. In one embodiment, at least a portion of the sensed position data <NUM> is obtained from a satellite-based position location system (e.g., GPS) and may be received by the computer processing system <NUM> in substantially real-time by a suitable data acquisition system (not shown). In other embodiments, the configuration of the particular system (e.g., network) may introduce some amount of delay in transmitting the sensed position data <NUM> to the computer processing system <NUM>.

The computer processor <NUM> may also be operatively connected to a pre-processing algorithm <NUM>, a real-time snapping algorithm <NUM>, and a user interface <NUM>. User interface <NUM> may include a display system <NUM>. As will be described in much greater detail herein, the computer processor <NUM> may use or implement the pre-processing algorithm <NUM> from time-to-time to prepare the terrestrial data <NUM> for further processing by the real-time snapping algorithm <NUM>. The pre-processing algorithm <NUM> may also be used to perform coordinate system conversions and to correct position location data to compensate for factors that may introduce spatial bias or other inaccuracies between the two data sets. The real-time snapping algorithm <NUM> may be used to correlate the sensed position data <NUM> with the terrestrial features <NUM> in substantially real-time, i.e., as the various vehicles <NUM> move within the defined operational area <NUM>.

Referring now to <FIG>, computer processor <NUM> may implement a method <NUM> to correlate sensed position data <NUM> with the terrestrial features <NUM>. In this regard it should be noted that it is generally preferred, but not required, that the correlation process of the present invention be conducted in real-time or substantially real-time. Such real-time correlation will allow correlated data to be used immediately by operators and/or other systems to improve operational efficiencies or to provide other benefits now known in the art or that may be developed in the future that would require or benefit from such real-time correlation.

The first series of steps in method <NUM> may be related to the implementation of the pre-processing algorithm <NUM> (<FIG>). As mentioned above, the pre-processing algorithm <NUM> maybe used to prepare the terrestrial data <NUM> for further processing by the real-time snapping algorithm <NUM>. Such data preparation may include, for example, the creation of snap points <NUM> (<FIG>), from the terrestrial data <NUM>. Pre-processing algorithm <NUM> may also be used to perform any coordinate transformations that may be required or desired to ensure that the terrestrial data <NUM> are in the same coordinate system as the sensed position data <NUM>. Pre-processing algorithm <NUM> may also be used to determine whether any correction of the terrestrial data <NUM> is required to compensate for any significant variance or spatial bias that may be detected between the two data sets (i.e., the sensed position data <NUM> and the terrestrial data <NUM>). In one embodiment, computer processor <NUM> is configured or programmed to implement the pre-processing algorithm <NUM> each time the terrestrial database <NUM> is updated. In one embodiment, the terrestrial database <NUM> is updated on a daily basis. Therefore, computer processor <NUM> implements the pre-processing algorithm <NUM> on a daily basis.

After the pre-processing algorithm <NUM> has been implemented, computer processor <NUM> may then use or implement the real-time snapping algorithm <NUM> in order to correlate the sensed position data <NUM> and terrestrial features <NUM> in substantially real-time. As used herein, the term real-time means that the correlation process can be completed with respect to each sensed position point <NUM> sufficiently quickly to allow a user or other systems (not shown) to make meaningful use of the correlated data without significant delay. By way of example, in one embodiment, the computer processor <NUM> is able to perform the correlation with a delay (i.e., latency), of less than about <NUM> second between the time at which a sensed location or position fix <NUM> is provided to computer processor <NUM> and when the correlation, i.e., the snapping of the sensed position point <NUM> to the best snap point <NUM> is complete. As will be described in much greater detail herein, the real-time snapping algorithm <NUM> is able to perform the correlation or snapping function in substantially real-time due to the effective 'pre-filtering' of snap points <NUM>. The pre-filtering of snap points <NUM> produces a reduced set <NUM> of snap point candidates <NUM> (<FIG>). The reduced set <NUM> of snap point candidates <NUM> significantly reduces the number of snap points <NUM> that must be analyzed, thereby significantly reducing the time required to perform the correlation.

The accuracy of the correlation or snapping function is improved by choosing the best snap point <NUM> (<FIG>) based on a plurality of predictive variables PV<NUM>-<NUM> and corresponding weighting factors w<NUM>-<NUM> (see Equation <NUM>). As will also be described in much greater detail herein, the predictive variables PV<NUM>-<NUM> and corresponding weighting factors w<NUM>-<NUM>, are used to calculate a score for each snap point candidate <NUM> in the reduced set <NUM> of snap point candidates. The calculated score is then used to select or choose the best snap point candidate <NUM> from among the snap point candidates <NUM> in the reduced set <NUM> of snap point candidates. The best snap point candidate <NUM> represents the best correlation between the sensed position data <NUM> and terrestrial features <NUM> for the particular sensed location or position fix <NUM>. The various steps of process <NUM> may be repeated on subsequent sensed locations or fixes <NUM> to correlate the sensed position data <NUM> from the moveable object or vehicle <NUM> with the terrestrial features in substantially real time. The correlation process therefore allows the position of the vehicle(s) <NUM> to be accurately tracked over time as it moves within the defined operational area <NUM>. If desired, the sequential vehicle positions and correlated terrestrial features <NUM> may be displayed on the display system <NUM> to provide a user with a substantially real-time indication or depiction of the vehicle <NUM> as it moves within the defined operational area <NUM>, as depicted in <FIG>.

A significant advantage of the present invention is that it may be used to accurately and rapidly (i.e., in substantially real-time) correlate the sensed position data <NUM> with terrestrial features <NUM>. The ability to perform the correlation in substantially real-time allows the correlated data to be used in ways and to realize advantages not possible in systems wherein the correlations are not made in real time. For example, besides allowing system operators to view the movement of vehicles and other moveable objects in substantially real-time, and in correct relation to the terrestrial features, the real-time correlations provided by the present invention can be used by other systems now known in the art or that may be developed in the future to improve the operation, deployment, efficiency, or productivity of the tracked vehicles and moveable objects.

Still other advantages are associated with the pre-filtering processes associated with the methods disclosed herein. For example, the pre-filtering processes substantially reduce the processing resources required to perform the correlations, thereby speeding the correlations so that they can be produced in substantially real-time. Alternatively, the reduction in processing resources will permit the use of lower performance computer systems to be used, which are typically much less expensive to procure and operate.

Still yet other advantages are associated with the use of the predictive variables and corresponding weighting factors to select the best snap point candidate. For example, we have discovered that highly accurate correlations can be made based on a relatively few predictive variables. In the particular embodiments shown and described herein, four (<NUM>) predictive variables provide highly accurate correlations, while again reducing the processing resources required to perform the correlations. The use of corresponding weighting factors also increases the accuracy of the correlations by providing the appropriate weight to the predictive variables. This ensures that those predictive variables that are more important in the selection of the best snap point candidates are weighted more heavily compared with variables that, while still important, have reduced levels of importance.

Having briefly described certain exemplary embodiments of systems and methods as well as some of its more significant features and advantages, various embodiments and variations will now be described in detail. However, before proceeding the description, it should be noted that while various embodiments are shown and described herein as they could be used to correlate sensed position data <NUM>, such as satellite position data, with terrestrial data <NUM> in a mining environment <NUM>, the present invention is not limited to use with such data types and in such environments. For example, the sensed position data <NUM> need not comprise satellite position data but instead could comprise position data derived by other means, such as by inertial- or ground-based navigation systems. Also, while the present invention may be used to advantage in open pit mining environments <NUM> where it is difficult to obtain accurate and reliable position data <NUM> and where terrestrial features <NUM> are prone to frequent movement or relocation, the present invention could be used in any of a wide range of environments and for any of a wide range of purposes, some of which are described herein and others of which would become apparent to persons having ordinary skill in the art after having become familiar with the teachings provided herein. Consequently, the present invention should not be regarded as limited to use in any particular type of position data, environment, or applications.

Referring back now to <FIG>, one embodiment of the position correlation system <NUM> may comprise a computer processor or computer processing system <NUM> that is operatively connected to the various databases, systems, and algorithms described herein. The various algorithms may be embodied in various software programs, modules, or applications provided on non-transitory computer-readable storage media (not shown) accessible by computer system <NUM>. The various software programs, modules, or applications may be provided with computer-executable instructions that, when executed by the computer system <NUM>, cause the computer system <NUM> to process information and data in accordance with the various methods and algorithms described herein.

Computer system <NUM> may comprise any of a wide range of general purpose programmable computer systems now known in the art or that may be developed in the future that are, or would be suitable for the intended application. However, because such computer systems are well-known in the art and could be readily provided by persons having ordinary skill in the art after having become familiar with the teachings provided herein, the particular computer system <NUM> that may be used in the embodiments shown and described herein will not be described in further detail.

Computer system <NUM> is operatively connected to the terrestrial database <NUM> and, optionally, the position database <NUM>. The terrestrial database <NUM> may comprise terrestrial data <NUM> that identifies at least the locations of desired terrestrial features <NUM>, although terrestrial data <NUM> could comprise data relating to other features or aspects of the terrestrial features <NUM> as well. Similarly, the position database <NUM> may comprise the sensed position data <NUM> associated with the various moveable objects, mining equipment and/or vehicles <NUM> operating in the defined operational area <NUM>. Computer processing system <NUM> may also be operatively associated with the pre-processing algorithm <NUM> and the real-time snapping algorithm <NUM>. Computer processing system <NUM> also may be operatively connected to the user interface system <NUM> to allow one or more users (not shown) to operate the computer system <NUM>. User interface system <NUM> may also comprise display system <NUM>, which may be used to provide a visual display of the correlated data and other aspects of the system <NUM>, as depicted in <FIG>. Computer system <NUM> also may be connected to a wide range of ancillary systems and devices, such as network systems, data acquisition systems, memory systems, algorithm modules, and additional databases as may be required or desired for the particular application. However, because such ancillary systems and devices are also well-known in the art and could be readily provided by persons having ordinary skill in the art after having become familiar with the teachings provided herein, the various ancillary systems and devices that may be required or desired for any particular application will not be described in further detail herein.

Considering now the various databases, the terrestrial database <NUM> may comprise terrestrial data <NUM>. Terrestrial data <NUM> may comprise a plurality of records or data files that identify and locate the position of various terrestrial features <NUM> within the defined operational area <NUM>. As mentioned earlier, the terrestrial features <NUM> may include, but are not limited to, the road network <NUM> which is defined by a plurality of roads <NUM>. Terrestrial features <NUM> may also include information and data relating to any desired components of the mining infrastructure system <NUM>, such as various service buildings, fueling stations, loading stations, dump stations, stockpiles, and the like. The terrestrial data <NUM> may comprise highly accurate position data, typically produced by land-based survey systems (not shown), that locate the positions of the terrestrial features <NUM> within the defined operational area <NUM>. The terrestrial survey data <NUM> may be updated from time-to-time (e.g., once every <NUM> hours) as necessary to reflect changes or re-locations of the various terrestrial features <NUM>.

The terrestrial data <NUM> may be provided in any of a variety of forms, data structures, and coordinate systems depending on the particular application and system used to generate the terrestrial data <NUM>. Consequently, the present invention should not be regarded as limited to any particular forms, data structures, and coordinate systems for such data. By way of example, in one embodiment, the various roads <NUM> comprising the road network <NUM> (<FIG>) are divided into a plurality of sections or segments, each of which is defined by a Bézier curve <NUM> having two end points <NUM>, <NUM> and two control points <NUM>, <NUM>, as best seen in <FIG>. The locations of the various end points <NUM>, <NUM> and control points <NUM>, <NUM>, maybe stored or provided in a mine coordinate system.

The position database <NUM> may comprise position data <NUM>. The position data <NUM> may comprise a plurality of records or data files of information and data that identify or locate the positions of the various moveable objects or vehicles <NUM> within the defined operational area <NUM>, as already briefly described. Each desired piece of equipment or vehicle <NUM> may be provided with a position sensing system (not shown) that senses the position of the vehicle <NUM> as it operates within the operational area <NUM>. In the embodiments shown and described herein, the position sensing system may comprise a satellite-based position sensing system, such as the global positioning system (GPS). Alternatively, the position data <NUM> may be obtained from other types of position sensing systems, such as from inertial sensing systems or ground-based radio navigation systems. Consequently, the present invention should not be regarded as limited to any particular type of position sensing system for producing the position data <NUM>.

In a typical application, the position data <NUM> derived from the position sensing systems (not shown) provided on the various vehicles <NUM> may be transmitted to a data acquisition system (not shown) via a wireless network (also not shown). Alternatively, other systems, devices, and configurations may be used. The data acquisition system may comprise a portion of computer system <NUM>, although it need not be. Thereafter, the position data <NUM> may be reformatted and processed, if necessary or desired, before being placed into the position database <NUM>. In this regard it should be noted that, in certain embodiments, the provision of a position database <NUM> is not strictly required. In such embodiments, the computer system <NUM> may receive the position data <NUM> directly, without saving the position data first in a database. However, as a practical matter, the position data <NUM> will nearly always be saved in some sort of memory system or database, if only on a temporary basis. Regardless of the configuration of the particular system, in one embodiment the computer processor <NUM> is able to access the position data <NUM> in substantially real-time, so that the correlation process can be performed in substantially real-time.

It should be noted that in most embodiments the position data <NUM> will not be continuous but will instead comprise a plurality of individual sensed locations or position fixes <NUM> collected over time on a periodic basis (e.g., once per second), as best seen in <FIG>. That is, the position data <NUM> will comprise time-based or temporal position data. Therefore, each individual sensed location or position fix <NUM> may also include a time stamp that correlates the sensed location or position fix <NUM> with the time at which the position fix <NUM> was obtained.

Other information and data may be associated with each position fix <NUM>. For example, in one embodiment, each position fix <NUM> may also include data relating to the heading of the vehicle <NUM> at the time of the position fix. Such vehicle heading data are used by the real-time snapping algorithm <NUM> to improve the accuracy of the correlation process. The position data <NUM> may be provided in any of a wide range of coordinate systems. In one embodiment, the position data <NUM> are provided in a 'GPS' coordinate system, comprising latitude, longitude, and altitude.

As is known, there may be significant errors and uncertainties in the position data <NUM> and it is not uncommon for a given position fix or sensed location point <NUM> to be in error by several tens, if not hundreds, of meters, particularly if the position data <NUM> are derived from a satellite-based position location system. These errors and uncertainties make it difficult to establish the exact location of a vehicle <NUM> moving within the defined operational area <NUM> and to correctly locate it with respect to known terrestrial features <NUM>. For example, if the mining environment <NUM> comprises an open pit mine, e.g., with equipment or vehicles <NUM> traveling on roads <NUM> within the mine, satellite-based position data <NUM> may not reliably fix the location of the vehicle <NUM> on a known road <NUM>, even though the vehicle <NUM> is actually traveling on the known road <NUM>. An example of such a circumstance is depicted in <FIG>, in which many of the sensed location points or position fixes <NUM> are actually located outside the boundary of the particular road <NUM> on which the vehicle <NUM> was operating.

Referring now primarily to <FIG>, the pre-processing algorithm <NUM> may be used to prepare, at step <NUM>, the terrestrial data <NUM> for further processing by the real-time snapping algorithm <NUM>. A first step <NUM> (shown in <FIG>) in the preparation process <NUM> (shown in <FIG> and <FIG>) involves the extraction of terrestrial data <NUM> from the terrestrial database <NUM>. In an embodiment wherein the vehicles <NUM> are to be tracked as they move along various roads <NUM> of road network <NUM>, the extraction process <NUM> may involve the extraction of the relevant road data from the terrestrial database <NUM>. The road data will then form the basis for the subsequent correlation of the positions of vehicles <NUM> as they move along the various roads <NUM> of road network <NUM>. Of course, additional data could be extracted from the terrestrial database <NUM> as may be required or desired in any particular application or circumstance.

Once the appropriate terrestrial data has been extracted (at step <NUM>) from the terrestrial database <NUM>, process <NUM> then creates, at step <NUM>, a plurality of snap points <NUM>. See also <FIG>. In the particular embodiment shown and described herein, each road <NUM> of road network <NUM> is represented and stored as a plurality of contiguous sections or segments, each of which is defined by a Bézier curve <NUM> having two end points <NUM>, <NUM> and two control points <NUM>, <NUM>, as best seen in <FIG>. Snap points <NUM> for each Bézier curve <NUM> may be created by dividing the Bézier curve <NUM> into a predetermined number of intervals. In one embodiment, the predetermined number of intervals correspond to a terrestrial distance of about <NUM> (about <NUM> ft). Alternatively, other intervals could also be used. Each snap point <NUM> is then assigned a location ID which, in one embodiment, comprises a start endpoint, an end endpoint, a distance from the end point <NUM> of Bézier curve <NUM>, and a distance to the end point <NUM> of Bézier curve <NUM>. Thus, each location ID defines the location of each snap point <NUM> on a specific Bézier curve <NUM> in the mine coordinate system.

Once all of the snap points <NUM> have been created, process <NUM> then proceeds to step <NUM> in which a number of predictive variable parameters are calculated for each snap point <NUM> created by step <NUM>. In one embodiment, the predictive variable parameters for each snap point <NUM> include the tangent angle <NUM> (e.g., as measured from true north) of the snap point <NUM>, the local road curvature <NUM> (e.g., in units of m-<NUM>) at the snap point <NUM>, as well as the intersection type, e.g., the number of other snap points <NUM> that are connected to the particular snap point <NUM>. For example, a snap point <NUM> located at a road intersection may be connected to <NUM> or more other snap points <NUM> on other roads <NUM>, as depicted in <FIG>.

Referring back now to <FIG>, if necessary, the pre-processing algorithm <NUM> may also convert, at step <NUM>, the coordinate system of the terrestrial data <NUM> into the coordinate system of the sensed position data <NUM>. For example, in an embodiment wherein the terrestrial data <NUM> are provided in a mine coordinate system and wherein the sensed position data <NUM> are provided in a GPS coordinate system (i.e., latitude, longitude, and altitude), then step <NUM> may be performed to convert the mine coordinate system of the terrestrial data <NUM> into the GPS coordinate system. Any of a wide range of coordinate transformation algorithms now known in the art or that may be developed in the future may be used for this purpose. However, since processes for performing such coordinate transformations are well-known in the art and could be readily provided by persons having ordinary skill in the art after having become familiar with the teachings provided herein, the particular coordinate transformation process used in conjunction with the present invention will not be described in further detail herein. Finally, it should be noted that step <NUM> may be performed before or after step <NUM>, depending on any of a wide range of factors and considerations. Therefore, pre-processing algorithm <NUM> should not be regarded as limited to performing the coordinate transformation step <NUM> in any particular order.

Depending on assumptions made when the mine site was developed and the terrestrial data <NUM> created, there may be spatial biases or other incongruities between the two data sets (e.g., the sensed position data <NUM> and the terrestrial data <NUM>). Correction process <NUM> may be implemented to correct for the bias or other incongruity between the two data sets.

With reference now to <FIG>, <FIG>, and with occasional reference to <FIG>, a first step <NUM> in correction process <NUM> involves 'overlaying' the snap points <NUM> created for the road network <NUM> with a plurality of sensed position points <NUM> collected from the position sensing systems of the various vehicles <NUM>. A schematic depiction of the two data sets (e.g., the terrestrial data <NUM> and sensed position data <NUM>) that are representative of the same terrestrial feature <NUM> (e.g., portion of a road <NUM>), are depicted in <FIG>. After being overlain on one another, various location parameters (e.g., latitude, longitude, and rotation) of the sensed position data <NUM> are iteratively varied at step <NUM> to optimize the overlap of the two data sets, as best seen in <FIG>. Because there will rarely be an optimal "fit" between the snap points <NUM> and the sensed position points <NUM> of the two data sets, the correction process <NUM> determines the magnitude, at step <NUM>, of the iterative variations required to optimize the overlap. If the magnitude of any of the location parameters exceeds a predetermined threshold for that parameter (e.g., as determined at step <NUM>) for a predetermined time (e.g., e.g., as determined at step <NUM>), then the correction process <NUM> will correct, at step <NUM>, the mapping between the two data sets. Otherwise, no correction will be applied.

By way of example, if the magnitude of the differences between the latitude or longitude of the two data sets exceeds <NUM> degrees, or if the difference between the rotation required to align the data sets exceeds <NUM> degrees, for a time period of <NUM> consecutive days, then the mapping will be corrected at step <NUM>.

As mentioned earlier, the computer processor <NUM> may use or implement the pre-processing algorithm <NUM> from time-to-time (e.g., each time the terrestrial data <NUM> are updated) to prepare the terrestrial data <NUM> for further processing by the real-time snapping algorithm <NUM>. Once this pre-processing has been performed, the computer processor <NUM> may implement the real-time snapping algorithm <NUM> to correlate the sensed position data <NUM> and terrestrial features <NUM>. The real-time snapping algorithm <NUM> may be used on a continuous basis (i.e., in which the various steps thereof are repeated in a loop, as depicted in <FIG>) so that the sensed position data <NUM> are correlated with the terrestrial features <NUM> on a continuous basis and in substantially real-time as the vehicle(s) <NUM> move within the defined operational area <NUM>.

Referring now to <FIG> and <FIG>, a first step <NUM> (<FIG>) in the real-time grid snapping algorithm <NUM> is to receive position data <NUM> from one or more vehicles <NUM> operating within the defined operational area <NUM>. Depending on the configuration of the particular system, the position data <NUM> may be received directly from a position sensing system(s) operatively associated with the vehicle(s) <NUM>. Alternatively, the position data <NUM> may be received from a suitable data acquisition system (not shown) that first collects the position data <NUM> from the vehicles <NUM>. As described above, the position data <NUM> may comprise a plurality of individual sensed locations or position fixes <NUM> that may be obtained by the position sensing system from time-to-time (e.g., once per second). Each individual sensed location or position fix <NUM> may comprise information regarding the position or location of the vehicle <NUM> at the time of the position fix <NUM>, a time-stamp indicating the time the vehicle <NUM> was at the particular location, and the heading of the vehicle <NUM> at that particular time. Of course, the position data <NUM> for each individual sensed location <NUM> may comprise additional information, if desired.

After receiving the position data <NUM> (e.g., as a data stream on a substantially continuous basis), at step <NUM>, the real-time snapping algorithm <NUM> then proceeds to step <NUM> (<FIG>) in which a reduced set <NUM> of snap point candidates <NUM> are selected from among the snap points <NUM> previously created in step <NUM> (<FIG>). Step <NUM> thus involves a 'pre-filtering' of the snap points <NUM>, significantly reducing the number of snap points <NUM> that need to be analyzed.

Referring now to <FIG>, <FIG>, which define embodiments that fall under the scope of the invention. The 'pre-filtering' process of step <NUM> may involve the creation or establishment, at step <NUM>, of a two-dimensional grid <NUM>. Two-dimensional grid <NUM> is defined by a plurality of intersecting lines <NUM>, <NUM>. A vertex <NUM> is defined at each intersection point, as best seen in <FIG>. Before proceeding with the description, it should be noted that the two-dimensional grid <NUM> is an abstract construct only and is used by the computer system <NUM> to pre-filter the number of snap points <NUM> required to be analyzed. It is not an actual grid that is created in the defined operational area <NUM>. In one embodiment, the each set of intersecting lines <NUM>, <NUM> comprises a plurality of lines that are arranged in substantially parallel, spaced-apart relation. The set of lines <NUM> may comprise a plurality of 'horizontally' oriented lines, whereas the set of lines <NUM> may comprise a plurality of 'vertically' oriented lines. Thus, the two sets of intersecting lines <NUM> and <NUM> are generally perpendicular to one another. Alternatively, other arrangements are possible (e.g., in which the two sets of intersecting lines <NUM> and <NUM> are not perpendicular to one another), as would become apparent to persons having ordinary skill in the art after having become familiar with the teachings provided herein. Consequently, the two-dimensional grid <NUM> should not be regarded as limited to the particular configuration shown and described herein.

The spacings <NUM> and <NUM> between the respective sets of horizontal and vertical lines <NUM> and <NUM> may be selected to correspond to any of a wide range of terrestrial distances, with smaller distances generally resulting in a less 'granular' or higher resolution snapping process. However, smaller terrestrial distances may also increase processing time to the extent that the algorithm <NUM> is no longer able to produce the required correlations in substantially real-time. By way of example, in one embodiment, the spacings <NUM> and <NUM> between the respective sets of lines <NUM> and <NUM> correspond to a terrestrial distance of about <NUM> (about <NUM> ft). So configured, then, the two-dimensional grid <NUM> in one embodiment comprises a two-dimensional grid of squares, wherein the side of each grid square corresponds to a terrestrial distance of about <NUM> (about <NUM> ft). The locations of the lines <NUM>, <NUM>, and vertices <NUM> may be provided in the same coordinate system used for the position data <NUM> (e.g., a GPS coordinate system).

A next step <NUM> in the method or process <NUM> identifies the vertex <NUM> that is nearest to the particular sensed location or position fix <NUM>. In the example depicted in <FIG>, the nearest vertex <NUM> is the vertex <NUM>' located in the center of the two-dimensional grid <NUM>. Next, in step <NUM>, a search area <NUM> is defined based on the identified vertex <NUM>'. In one embodiment, the search area <NUM> is defined by the four (<NUM>) grid squares that share the identified vertex <NUM>'. Alternatively, the search area <NUM> could be defined by some other number of grid squares.

After the search area <NUM> has been defined (e.g., in step <NUM>), step <NUM> identifies as a set <NUM> of snap point candidates <NUM>, those snap points <NUM> that are contained within the search area <NUM>. In <FIG>, the set <NUM> of snap point candidates <NUM> comprises fifteen (<NUM>) individual snap points <NUM> defining that portion of the road <NUM> shown within the four (<NUM>) grid squares defining search area <NUM>. Because each snap point <NUM> within the search area <NUM> is regarded as a potential snap point for the particular sensed location or position fix <NUM>, the snap points <NUM> within the set <NUM> are referred to herein as `snap point candidates' <NUM>. While the pre-filtering process <NUM> could be terminated at this point, an additional filtering step may be conducted in order to further reduce the number of possible snap point candidates <NUM> to be analyzed.

Referring now to <FIG>, an additional filtering step <NUM> (<FIG>) may involve the identification of the reduced set <NUM> of snap point candidates <NUM>. The reduced set <NUM> of snap point candidates <NUM> is selected from the set <NUM> of snap point candidates <NUM> identified in step <NUM>. More specifically, the reduced set <NUM> of snap point candidates <NUM> is identified based on the snap point candidates <NUM> in the set <NUM> of snap point candidates that are within a predetermined distance <NUM> from the sensed position point <NUM>. In the particular example described herein, the reduced set <NUM> of snap point candidates <NUM> identified in step <NUM> reduces to six (<NUM>) the number of snap point candidates <NUM> that need to be considered or analyzed.

The predetermined distance <NUM> may be selected to correspond to any of a wide range of terrestrial distances, with smaller distances generally resulting in a less 'granular' or higher resolution snapping process. However, smaller terrestrial distances may also increase processing time to the extent that the algorithm <NUM> is no longer able to produce the required correlations in substantially real-time. It may also reduce by too large an extent the number of snap point candidates <NUM>, thereby possibly resulting in the failure to find a correlation. By way of example, in one embodiment, the predetermined distance <NUM> is selected to correspond to a terrestrial distance of about <NUM> (about <NUM> ft).

Referring back now primarily to <FIG>, <FIG>, and <FIG>, the next step <NUM> in the real-time snapping algorithm <NUM> chooses the best snap point candidate <NUM> (<FIG>) from among the snap point candidates <NUM> in the reduced set <NUM> of snap point candidates identified in step <NUM> (<FIG>). The best snap point candidate <NUM> is selected or chosen based on a plurality of predictive variables (e.g., PV<NUM>-<NUM>) and corresponding weighting factors (e.g., w<NUM>-<NUM>). Thus, the best snap point candidate <NUM> will not necessarily be the snap point candidate <NUM> that is located nearest to the particular sensed location point or position fix <NUM>, as depicted in <FIG>.

The predictive variables that we have identified as best predicting the appropriate correlation for the snap point data are referred to herein as "PV<NUM>-<NUM>," respectively, and are defined as follows:.

For the fourth predictive variable, Ω or PV<NUM>, we have developed special rules to be followed in two cases. The first case relates to the endpoint of a road segment, i.e., where a road <NUM> comes to an end. There is a discontinuity at a road endpoint. In addition, vehicles <NUM> usually turn around at a road endpoint. Therefore, the corresponding heading value for the corresponding position fix <NUM> could be any of a wide range of headings. Therefore, the endpoint of a road segment, specifically the last snap point <NUM> of the road segment, is assigned a null tangent angle <NUM> (<FIG>) in step <NUM> (<FIG>). Similarly, for a snap point <NUM> located at a road intersection, multiple tangent angles <NUM> exist for the multiple roads that pass through the snap point <NUM>. Thus, snap points <NUM> located at road intersections are also assigned a null tangent angle <NUM> in step <NUM>.

With reference now to <FIG>, a first step <NUM> of the choosing process or step <NUM> (<FIG>) is to determine the value of each predictive variable parameter for each snap point candidate <NUM> in the reduced set <NUM> of snap point candidates <NUM>. As described above, the predictive variable parameter for each snap point candidate <NUM> in the reduced set <NUM> may be determined in advance for all snap points <NUM>. In the particular embodiment shown and described herein, the predictive variable parameters were determined in step <NUM> (<FIG>) of pre-processing algorithm <NUM>.

The next step <NUM> in the choosing process <NUM> is to calculate a score for each snap point candidate <NUM> in the reduced set <NUM> (<FIG>) of snap point candidates. The score is based on the value of the predictive variables PV<NUM>-<NUM> and the weighting factors w<NUM>-<NUM> for each predictive variable. As described above, the value for each predictive variable may be determined from the predictive variable parameters for the sensed position point <NUM> and for the various snap point candidates <NUM>. For example, the predictive variable DGPS (i.e., PV<NUM>) may be obtained by calculating the terrestrial distance between the sensed position point <NUM> and each snap point candidate <NUM> in the reduced set <NUM> of snap point candidates. The values of the other predictive variables (i.e., PV<NUM>-<NUM>) may be obtained from the corresponding predictive variable parameters for the particular sensed position point <NUM> and each of the snap point candidates <NUM> in the reduced set <NUM> of snap point candidates. In the particular embodiment shown and described herein, the best snap point candidate <NUM> is identified in step <NUM> as the snap point candidate <NUM> having the highest score. Further, because in this particular example the reduced set <NUM> of snap point candidates contains only six (<NUM>) snap point candidates <NUM> (<FIG>), the selection process <NUM> need only be performed six (<NUM>) times, once for each snap point candidate <NUM> in the reduced set <NUM> of snap point candidates, thereby significantly reducing the number of computations that must be performed.

The weighting factors w<NUM>-<NUM> for the various predictive variables may be determined or calculated by performing a logistic regression. The weighting factors w<NUM>-<NUM> represent the predictive importance of the corresponding predictive variables PV<NUM>-<NUM>. In the particular embodiments shown and described herein, the weighting factors w<NUM>-<NUM> are determined or created from a `training set' before performing or implementing the real-time snapping algorithm <NUM>. The resulting weighting factors w<NUM>-<NUM> may then be stored in a suitable memory system or look-up table for use by the real-time snapping algorithm <NUM>.

Referring now to <FIG>, a first step <NUM> in calculating the weighting factors w<NUM>-<NUM> for the corresponding predictive variables PV<NUM>-<NUM> involves the creation of a `training set' of data from the sensed position data <NUM>. The training set may comprise a large number of sensed locations <NUM> obtained from the various moveable objects or vehicles <NUM> as they move throughout the defined operational area <NUM>. In one embodiment, the training set was created from position data <NUM> obtained over a <NUM> hour operational period. Alternatively, other times and/or number of sensed locations <NUM> may be used. Thereafter, the various individual sensed locations <NUM> in the training set maybe snapped to corresponding snap points <NUM>, e.g., at step <NUM>. The snapping process used may comprise the real-time snapping process described herein (but with corresponding weighting values for each predictive parameter set at a value of <NUM>, for example).

The sample snap points created from the training set may then be analyzed, at step <NUM>, to determine whether the snaps were correct or erroneous. In one embodiment, a snap point is regarded as correct if the sample snap path segment ID matched a batch path segment ID within a time window of <NUM> snap point events (e.g., <NUM> seconds where individual position fixes <NUM> are obtained once very second). Otherwise, the snap is regarded as incorrect. Thereafter, a logistic regression process is applied at step <NUM> to determine the appropriate weighing factor w<NUM>-<NUM> for the corresponding predictive variable PV<NUM>-<NUM>. The logistic regression process may involve the following equation: <MAT> where:.

Referring now to <FIG>, <FIG>, and <FIG>, the next step <NUM> in the real-time snapping algorithm <NUM> may involve snapping the particular sensed position point or fix <NUM> to the best snap point candidate <NUM> identified in step <NUM> (<FIG>). Thereafter, the snapped position point may be displayed, at step <NUM>, on display system <NUM> of user interface system <NUM>. Additional sensed position points or fixes <NUM> may be correlated and snapped by repeating the process <NUM>, the results of which also may be displayed on display system <NUM>, as best seen in <FIG>. So displaying the various snapped position points will cause the display system to provide a visual indication of the sequential positions of the moveable object or objects <NUM> with respect to the terrestrial features <NUM> in substantially real time.

For example, and as illustrated in <FIG>, various individual sensed locations or position fixes <NUM> produced by a moving vehicle <NUM> traveling various roads <NUM> in road network <NUM> may be displayed as they are received. Because the snapping process occurs in substantially real time, the display system <NUM> may also display the various snapped locations (i.e., the best snap points <NUM>), along with the various snap points <NUM> associated with the various roads <NUM> of road network <NUM>. The real-time snapping algorithm <NUM> is able to correlate or snap the various individual position fixes <NUM> to the correct snap points (i.e., the best snap points <NUM>) even though the vehicle <NUM> traveled through complex road intersections that could have easily resulted in incorrect correlations, i.e., snaps to incorrect snap points <NUM>. Also, note that many of the sensed locations or position fixes <NUM> depicted in <FIG> do not occur within the boundaries of the various roads <NUM> in road network <NUM>. This is an example of the position errors that commonly occur with a satellite-based position location system. Nevertheless, the correlation system <NUM> of the present invention was able to correctly correlate or snap the various out-of-bounds sensed locations or position fixes <NUM> to the snap points on the proper road <NUM>.

In addition to the substantially real-time display of the snapped position points <NUM>, the plurality of snapped position points <NUM> may be used to track sequential positions of the moveable object <NUM> over time and may be used by other systems now known in the art or that may be developed in the future to improve the operation, deployment, or efficiency of the vehicles <NUM> operating within the defined operational area <NUM>.

Claim 1:
A computer-implemented method (<NUM>) of correlating sensed position data (<NUM>) with terrestrial features (<NUM>), the sensed position data (<NUM>) comprising sensed position points, the terrestrial features (<NUM>) being located by terrestrial data (<NUM>), comprising:
receiving (<NUM>) the sensed position data (<NUM>) from a position sensing system operatively associated with a moveable object (<NUM>);
selecting (<NUM>) a reduced set (<NUM>) of snap point candidates (<NUM>) from the terrestrial data (<NUM>) based on a sensed position point (<NUM>), wherein said selecting (<NUM>) further comprises:
referencing a two-dimensional grid (<NUM>) comprising a plurality of intersecting lines (<NUM>,<NUM>) that define vertices (<NUM>) at intersection points of the intersecting lines (<NUM>, <NUM>), the two-dimensional grid (<NUM>) being defined by a coordinate system that corresponds to a coordinate system for locating the terrestrial features (<NUM>);
identifying (<NUM>) a vertex (<NUM>) of the two-dimensional grid (<NUM>) that is nearest to the sensed position point (<NUM>);
defining (<NUM>) a search area (<NUM>) based on the identified vertex (<NUM>);
selecting (<NUM>) as a set (<NUM>) of snap point candidates (<NUM>) all snap points (<NUM>) in the terrestrial data (<NUM>) that are within the defined search area (<NUM>); and
selecting (<NUM>) as the reduced set (<NUM>) of snap point candidates (<NUM>) all snap point candidates (<NUM>) in the set (<NUM>) of snap point candidates (<NUM>) that are within a predetermined distance (<NUM>) from the sensed position point (<NUM>);
choosing (<NUM>) a best snap point candidate from among the reduced set (<NUM>) of snap point candidates (<NUM>) based on a plurality of predictive variables and corresponding weighting factors for each snap point candidate (<NUM>) in the reduced set (<NUM>) of snap point candidates (<NUM>); and
snapping (<NUM>) the sensed position point (<NUM>) to the best snap point candidate to produce a snapped position point (<NUM>), wherein said selecting (<NUM>), said choosing (<NUM>), and said snapping (<NUM>) are performed in substantially real time so that said method (<NUM>) correlates the sensed position data (<NUM>) from the moveable object (<NUM>) with terrestrial features (<NUM>) in substantially real time.