Field of the invention

The present invention relates to a method and a device for determining the position of a moving object. The invention also relates to a computer program and a computer program product implementing the method according to the invention. The invention further relates to a moving object in the form of a mining and/or construction machine.

Background of the invention There exist various situations in which it may be desirable to accurately determine the position of an object. With regard to outdoor positioning, satellite based

positioning systems, such as GPS (Global Positioning System) are oftentimes utilized.

Oftentimes, however, there is a desire to accurately position objects also in

environments where satellite-based positioning systems may not be utilized, such as in indoor/underground environments. For example, objects for which an accurate positioning may be desirable may comprise any type of vehicle or machine operating in a mine or tunnel, or any other kind of objects operating in environments where satellite positioning is not available, e.g. in storage facilities such as warehouses. The positioning systems being used in such environments may typically be based on use of radio technologies. A common technique is use of triangulation based on signal strength measurements. In case a higher accuracy in the determining of the position is required, radio technologies that support time difference measurements of the time of arrival of signals sent to/from an object in combination with a plurality of radio access points may be utilized. Radio technologies that support one or both of the above mentioned positioning methods may comprise cellular radio access technologies (e.g. LTE), wifi, LoRa and UWB.

Although such positioning methods may be utilized to perform the desired

positioning, accurate positioning imposes requirements in regard of the radio infrastructure. For example, it needs to be ensured that all objects have sufficient radio coverage to calculate the positions. This, in turn, in combination with the target accuracy of the calculated positions, restricts the possible maximum inter-site distance between the radio access points when using triangulation technologies, which imposes costs in infrastructure. Furthermore, complicated environments, such as e.g. underground mines, typically require careful radio network planning and possibly dense deployments to allow high accuracy positioning to function properly.

Object of the invention and its most important features

It is an object of the present invention to provide a method and a device that makes possible an accurate determination of the position of an object being configured to move in an environment in which the object is constrained to follow a defined network of paths.

This and other objects are achieved according to the present invention by a method according to claim 1.

According to the present invention, it is provided a method for determining the position of an object being configured to move in an environment in which the object is constrained to follow a defined network of paths, the position of the object being determined by pattern matching between a first pattern representing a track of a movement undertaken by the object and a second pattern representing the environment in which the tracked movement has been undertaken by the object, the object track having a head and a tail, the head representing a current position of the object. The pattern representing the environment is a discretized pattern representing the environment, the network of paths being represented by a plurality of nodes representing positions in the network of paths. The method comprises:

when a matching error in the current position of the object exceeds a threshold, determining nodes of the pattern representing the environment for which pattern matching is to be carried out utilizing a non-pattern matching positioning method,

when the matching error in the current position of the object is below the threshold, determining one or more nodes of the pattern representing the environment for which pattern matching is to be carried out based on one or more nodes of the pattern representing the environment previously determined to be the position of the object, and

determining the current position of the object as a node for which the pattern matching results in a matching error below the threshold.

As was mentioned above, there oftentimes exists a general desire to be able to accurately position objects in environments where navigation systems such as e.g. GPS (Global positioning system) systems may not be utilized. This may e.g. be the case in mines and tunnels, as well as in warehouse facilities and other types of indoor facilities. In case a wireless network is utilized, to provide for sufficient accuracy in the positioning may, as discussed, give rise to undesirable costs and the required infrastructure may not be feasible possible to implement.

The present invention relates to positioning of an object, where the object is configured to move in an environment in which the object is constrained to follow a defined network of paths. This is in general the case indoors and underground, where e.g. the object is confined to follow paths such as roads/tunnels/drifts/galleries etc., in the following denoted paths, in an underground mine, a network of

maneuvering areas and/or a network of indoor roads (paths). According to

embodiments of the invention it is provided a solution that reduces the requirements regarding infrastructure in the environment in which the positioning is to be performed.

According to the invention, the position of the object is determined by utilizing pattern matching between a first pattern representing a track of a movement undertaken by the object, and a second pattern representing the environment in which the tracked movement has been undertaken by the object.

The object track has a head and a tail, where the head represents a current position of the object, and where the tail represents the oldest position of the object maintained in the object track. The pattern representing the environment being utilized in the pattern matching is a discretized pattern representation of the environment. The network of paths is represented by a plurality of nodes, where each node represents a position in the network of paths of the environment. For example, the nodes may be on mutually equal distances from each other along the, oftentimes plurality of, paths of the environment. The inter-node distance, may, however, also be arranged to differ, e.g. in dependence of curvature of the paths of the environment, where e.g. a smaller distance between nodes may be utilized for smaller radiuses in curvatures. The pattern representation of the environment may, for example, be a discretized two-dimensional representation of the network of paths of the

environment. The pattern representation of the environment may, however, also be a three-dimensional representation of the environment, e.g. taking also elevation into account.

According to the invention, a matching error is determined in the pattern matching. This matching error may represent a discrepancy between an estimated track of the object in relation to a portion of the pattern representing the environment, and is hence is a measure of the accuracy in the position of the object. In case no pattern matching has yet been performed, the matching error will be high, and also e.g. be set to a predetermined value. The matching error may be determined in any suitable manner. According to the invention, when a matching error in the current position of the object exceeds a threshold, nodes of the pattern representing the environment for which pattern matching is to be carried out is determined utilizing a non-pattern matching positioning method. This may be the case, for example, if pattern matching has not been previously performed, e.g. for a period of time or at all, for the object, or when otherwise the position of the object is not known to an extent where the matching error is below the threshold, e.g. if the matching error increases during ongoing positioning using pattern matching.

In general, pattern matching may impose a high computational load, and if all nodes of a pattern representing the environment needs to be matched as a possible position of the head of the object track, this may take time and possibly also result in false positive matches e.g. in case the environment has a repetitive design or otherwise exhibits portions having paths of similar forms. According to the invention, as mentioned, the computational load is reduced and as is the risk of determining the position of the object to be some other position than where the object in reality is by using a non-pattern matching positioning method for determining a portion of the pattern representing the environment for which the pattern matching is to be carried out. In this way the number of nodes of the pattern of the environment to be tested in pattern matching may be substantially reduced in relation to the overall number of nodes being present in the pattern of the environment. This may substantially speed up calculations and also substantially reduce the risk for false positives.

When, on the other hand, the matching error in the current position of the object is below the threshold, the one or more nodes of the pattern representing the

environment for which pattern matching is to be carried out is, instead, determined based on one or more nodes of the pattern representing the environment previously determined to be the position of the object. In this case, the position of the head of the object track may have been determined to a node, and the subsequent position of the object is likely to be a node in the vicinity of the node that has been determined as the object position.

With regard to the nodes these may be represented, e.g. by an identity, such as, for example, a sequence number or any other suitable identity, and a position in the environment, e.g. stated in coordinates, such as coordinates of a global coordinate system of the environment, and where the coordinates may be stated in two or three dimensions. Furthermore, the representation of the nodes may also include information regarding which nodes that are neighbors to a particular node. The number of neighboring nodes may be higher for a node located in an intersection of crossing paths than for a node along a single path. The nodes may be represented by a data structure comprising the above information. This allows straightforward search for all nodes of the environment e.g. within a certain distance from a particular node, and also straightforward and simple searches for e.g. neighboring nodes of a particular node.

The representation of the object track may also be a discretized track represented by a sequence of nodes along the track, where each node comprises a position, such as coordinates of a coordinate system, where the position may be stated in relation to the preceding node and/or the subsequent node and/or other nodes. The object track may be less complex than the representation of the environment, since the object track will be a simple sequence of nodes without branches.

With regard to the object track, a node may be added to the sequence of nodes each time the object has moved a predetermined distance, such as a predetermined number of meters, e.g. any distance in the interval 0.1 -10 meters. The added node will represent the most recent motion of the object, thereby forming a new head of the object track, and the nodes of the object track may be ordered to reflect the order of addition of a node in relation to the previously added node.

The object track may be determined using a gyroscope and/or one or more accelerometers to determine turning motions of the object. This may be used in combination with a signal representing the speed of the object in order to estimate the object track in terms of travelled distance and turning motions, where the object track may e.g. be estimated in two or three dimensions.

It is in general desirable to have an object track that at least is of a predetermined minimum length in order to reduce the risk for false positive matches with other parts of the environment than where the object currently is present. Pattern matching may also be configured to be performed only when the representation of the object track has reached a predetermined number of nodes thereby indicating an object track having at least a predetermined length. If the length is too short, the risk for false matches increases.

Still it may not be feasible to allow the object track to comprise all motions made by the object, i.e. the full distance travelled by the object. According to embodiments of the invention, when the number of nodes of the object track, and/or length of the object track, has reached a first predetermined number of nodes and/or first length, the node representing the tail of the track, i.e. the oldest node, may be discarded when a new node, representing a new head of the track, is added.

When performing the pattern matching for a position represented by a node of the environment, the head of the object track may be positioned in this node, and nodes of the object track, such as all of, or at least a predetermined number of the nodes of the object track, are then compared with corresponding nodes of the pattern representing the environment along a path extending from the node being evaluated in regard of being a possible position of the object. The differences in positions between corresponding nodes are then used to calculate a matching error, where the matching error hence takes into account differences in positions between the pairs of nodes, respectively.

Hence, when matching the object track with nodes of the pattern representing the environment, a node of the pattern representing the environment may be assumed to represent a current position of the head of the object track, and a matching error representing an aggregate of differences in positions between consecutive nodes of the object track and corresponding consecutive nodes of the pattern representing the environment may then be determined, wherein the matching error is determined for a plurality of assumed positions (nodes) of the head of the object track, and wherein the position of the head of the object track may be determined to be the position of the node in the pattern representing the environment for which the pattern matching exhibits the smallest matching error.

This pattern matching may be performed for a plurality of nodes of the environment, and the position of the object may then be determined to be the position of the node of the pattern representing the environment for which pattern matching, with the head of the track in said node, exhibits the smallest matching error.

According to embodiments of the invention, the matching error may, for example, be determined using a likelihood function, such as a log-likelihood function, or in any other suitable way, where e.g. older nodes of the object track may be given less weight than more recently added nodes when calculating the matching error.

Furthermore, when performing pattern matching for a node of the pattern

representing the environment, the object track may be rotated through a plurality of different angles, and the pattern matching may be performed for each of the rotations, wherein the angle resulting in the smallest matching error may be determined to represent the actual object track. In this way differences in rotations of the coordinate system of the environment and the coordinate system of sensors being used in determining the object track may be taken into account. The angle resulting in the smallest matching error may also be utilized to compensate for sensor signals being used to determine the object track, and/or calibrate sensors providing sensor signals being used in the determination of the object track.

When the position of the head of the object track has been determined to a first node of the pattern representing the environment, the position of the head of the object track following a further motion of the object may be determined utilizing incremental pattern matching. That is, a pattern matching in which the subsequent position of the head of the object track is presumed to be a neighbor node of said first node of the pattern representing the environment in a direction of motion of the object. In this way, continued determination of the position of the object can be carried out in an efficient manner with little computational load, still giving a high accuracy in the estimation of the position.

The direction of motion of the object may be determined by assuming that the current object track head position will be in the assumed direction of travel from the last successfully obtained position of the algorithm.

If the matching error resulting from incremental pattern matching exceeds a

threshold, pattern matching may be extended to one or more nodes further away in the assumed direction of travel, and/or to one or more nodes in a direction opposite the currently assumed direction of travel of the object. This may account for situations where matching with only the next node in the direction of travel provides poor results, but where the object still is close to this node, so that the determination of the position may still be performed with high certainty without reverting to full pattern matching.

Alternatively, or in addition to utilizing the incremental pattern matching, the object track head position may be estimated using dead reckoning pattern matching, where the position of the object is determined using an estimation of the distance travelled from node of the pattern representing the environment that has been determined as the position of the object. Dead reckoning pattern matching may be advantageous to use e.g. when the environment exhibits little change in the segment in which the object is present. For example, the turning radius of a bend may be constant, or the path follow a straight line.

When the matching error is below a predetermined threshold for a node, and the node hence being determined as the position of the object, this node may be stored as a position for use as start in dead-reckoning pattern matching and/or incremental pattern matching.

The dead reckoning pattern matching may also be carried out in parallel with the incremental pattern matching or extended incremental pattern matching, wherein the estimated matching errors from the incremental pattern matching or the extended incremental pattern matching and the dead-reckoning pattern matching may be compared, and the match providing the smallest matching error be selected as a determination of the position of the object.

If the matching error obtained from any one or more from incremental pattern matching, extended incremental pattern matching and dead-reckoning pattern matching exceeds a threshold nodes of the pattern representing the environment for which pattern matching is to be carried out may again be determined utilizing a non pattern matching positioning method to ensure that the position is determined with a satisfying degree of certainty.

When the object track is determined using e.g. a gyroscope and/or acceleration sensors and object speed data, this data does not necessarily indicate whether the object is moving in a forward or reverse direction. Object speed signals may be absolute, and not distinguish between direction of travel. Also, such information may not be easy to determine from gyroscope and/or accelerometer sensor signals. For example, it may not be possible to determine whether the object is retarding in a forward direction of travel or accelerating in a reverse direction of travel.

According to embodiments of the invention, therefore, in order to obtain a vehicle track that corresponds to the actual object motions, object tracks are generated for both travel in the assumed direction of travel, but also in the opposite direction of travel. In this way it may be concluded that the object has changed direction of travel when the track representing the opposite direction of travel results in the least matching error.

Such reverse direction of travel tracks may be arranged to be always contemplated, or only in situations where it is found that the matching error in incremental pattern matching suddenly increases.

According to embodiments of the invention, the reverse direction of travel is only contemplated when signals from gyroscope/acceleration sensors indicate a possible change in direction of travel, and/or when the object has stopped and again been set in motion. According to embodiments of the invention, the direction of travel is determined by determining a gear ratio of a current gear of a gearbox of the object. The gear ratio may be estimated, for example, by dividing the speed of rotation of a power source of the object with a speed of the object, and the obtained ratio may then e.g. be compared with gear ratios being utilized in a gearbox of the object, which may e.g. be stored in a control system of the object.

According to embodiments of the invention, other signals of a control system of the object may also be utilized, such as e.g. signals indicating that a reversing light is being active.

The pattern representing the environment may be a discretized 2D or 3D map of the environment, and the non-pattern matching positioning method may be any suitable kind of non-pattern matching positioning method, such as a light or radio wave based positioning method.

The matching error of the current position of the object may be determined in any suitable manner, such as by an accuracy determined by a distance in meters within which the object is presumed to be present, and/or a matching error calculated from the pattern matching.

The position of the object may be transmitted to an object external location for further transmission to other objects operating in the environment, where the object may be configured to receive positions of other objects in the environment. The positions of the object, and said other objects, may be configured to be displayed on a display, e.g. for a person present in the object.

The non-pattern matching positioning method may, for example, be a light or radio wave based positioning method. The above described method features may also be implemented to be carried out by a device, and hence corresponding advantages are obtained by corresponding device/system features.

According to embodiments of the invention, the invention is implemented in a consumer tablet or smartphone device, where the consumer tablet or smartphone device may be configured to receive vehicle speed signals from a control system of the vehicle using a standardized interface.

The invention also relates to a vehicle or other kind of object that may move around in an environment, such as any kind of mining and/or construction machine.

Further characteristics of the present invention and advantages thereof are indicated in the detailed description of exemplary embodiments set out below and the attached drawings.

Brief description of the drawings

The invention will now be described more in detail in view of an exemplary embodiment and by means of the appended drawings, in which: Fig. 1 schematically illustrates vehicle/machine in which embodiments of the invention may be utilized;

Fig. 2 schematically illustrates a portion of a mine;

Fig. 3 schematically illustrates the portion of the mine as a discretized 3D map;

Fig. 4 illustrates an exemplary map data structure of the nodes of fig. 3; Fig. 5 illustrates a vector representation of a track of an object; Fig. 6 illustrates an exemplary method according to embodiments of the invention; Fig. 7 illustrates selection of nodes for full pattern matching;

Fig. 8 illustrates pattern matching between a track of an object and nodes of the map in fig. 3; Fig. 9 illustrates paths of different nodes to be matched to the track of the object;

Fig. 10 illustrates a method for performing full pattern matching.

Fig. 1 1 illustrates a method for performing incremental pattern matching.

Fig. 12 illustrates a method for performing dead reckoning pattern matching.

Detailed description of exemplary embodiments Embodiments of the invention may be utilized for determining the position of any kind of object moving around in an environment where the movements of the object are constrained to follow a defined network of paths. In the following, however, embodiments of the invention will be exemplified for an object in the form of a vehicle, the vehicle being a mining and/or construction machine which moves around in an underground mine.

Fig. 1 illustrates an exemplary vehicle/machine 100 from the side and for which the position may be determined according to embodiments of the invention. The exemplified vehicle 100 constitutes a so-called LFID load machine, and is used to load and transport away material such as, for example, blasted rock or other material by means of a bucket 101. Vehicles of this kind may be arranged to operate autonomously, be operated by remote control, or by an operator being present in the vehicle. The invention may be utilized independent of the manner in which the vehicle is being controlled, although in the present example the vehicle 100 is assumed to be driven by an operator. In case the machine is autonomously operating, or controlled by remote control, the position of the machine may still be transmitted to e.g. a central location of the mine for further transmission to other vehicles in the mine, so that vehicles/machines being present in the mine may obtain information regarding the positions of other vehicles/machines operating in the mine.

The exemplary vehicle 100 is an articulated vehicle, where a front portion is connected to a rear portion by means of a hinge to be steered by means of articulated steering to facilitate maneuvering of the machine. It is to be noted that the illustrated machine is for exemplary purposes only and that the invention may be utilized in connection with any kind of machine/vehicle and hence also non- articulated vehicles. Furthermore, the vehicle 100 comprises wheels 102-103 and a control system comprising at least one control unit 106, which controls various of the functions of the vehicle. Vehicles of the disclosed kind may comprise a plurality of control units, where each control unit, respectively, may be arranged to be

responsible for different functions of the vehicle 100. A vehicle of the disclosed kind may also comprise e.g. means for wireless communication with a control center, e.g. to transmit determined positions of the vehicle, and receive positions of other vehicles for display e.g. on display means of the vehicle 100 in order to provide an onboard operator/driver with information of the location of other vehicles in the mine, where these locations may be presented e.g. on a map of the environment.

According to embodiments of the invention, the determining of the position of the vehicle 100 described below may be implemented in any suitable control unit of the vehicle, such as control unit 106. The control unit 106 may comprises a data processing unit which, based on received signals, and by means of suitable calculation may perform pattern matching according to embodiments of the invention described below, and may, for example, be constituted by a processor, such as a digital signal processor, which is controlled by means of a computer program product that is built into the processor or being connected thereto, such as a computer program generated by means of an appropriate programming language and being stored in a non-transitory computer memory.

According to embodiments of the invention, the determination of the position of the vehicle is, instead, configured to run on a standard consumer device, such as a smart phone or tablet device. This is also the case according to the present example, where a standard consumer device in the form of a tablet is connected to the vehicle, where this connection can be configured to be carried out e.g. through the use of a standardized interface, such as an OBDII interface or any other suitable interface. According to embodiments of the invention, the consumer device is connected to the vehicle in order to obtain data relating to the speed of the vehicle. In this case the consumer device may be configured to transmit and receive positioning data, and display the positions of other vehicles/machines to the operator.

According to embodiments of the invention, pattern matching is utilized to determine the position of the vehicle. This is performed by measuring and estimating, e.g. by calculating, the trajectory, track, of the manner in which the vehicle has moved over time, and this track is then matched to a representation, such as a 3D map, of the spatial network of paths the vehicle may move along in the environment in which it is present. A correlation between the estimated track of the vehicle and the map is then used to determine the current position of the vehicle 100.

Fig. 2 illustrates an example of a portion 200 of a representation of an environment, such as a mine, in which the vehicle 100 may be operating. The environment comprises a plurality of tunnels/roads/drifts/galleries etc. 201 -203, in the following denoted roads, in which the vehicle, as well as a plurality of other vehicles may move around. According to the present example, the representation of the environment in fig. 2 is a 3D map of the environment. The vehicle 100 is shown as presently being at a location 204. Fig. 2 also illustrates a radio transmitter 205 forming part of a wireless network of the mine.

The 3D map may, for example, be obtained from a CAD drawing of the environment, such as a CAD drawing of a mine. According to embodiments of the invention, the map of the environment is discretized. That is, instead of the environment being represented by a map comprising continuous lines such as in fig. 2, the map is converted to a spatial database. This may be performed by replacing the continuous lines with node objects, in the following denoted nodes, that represent specific positions along the lines in the map. This may be performed in a pre-determined manner, where a new node e.g. may be added for every 5 meters, in actual distance, along the middle of the lines in the map representing roads, i.e. in the middle of the road of the mine. Any other suitable inter-nodal distance may also be utilized, e.g. any distance in the range 0.1 -10m.

Fig. 3 illustrates an exemplary transformation 300 of the 3D map in fig. 2 to a discretized map comprising a plurality of nodes N1 , N2, ..., Nn, some of which being denoted in the figure.

The representation of the environment in the form of discretized map 300

consequently represents the environment (the mine according to the present example) in a less detailed format. On the other hand, this node representation may be used to form a map data structure, which is a mathematical structure modelling pairwise relations between nodes in the map graph. The map data structure may then be used to implement algorithms to search for nodes, find paths between two different nodes, or calculate a subset of nodes, where the subset of nodes e.g. may comprise nodes within a predetermined rad i us/di stance from a particular node.

Fig. 4 illustrates such a map data structure 400, where each node N1 , N2, N3, ..., Nn represents a defined physical point in space on the map. According to the present example, each node is represented by a node ID (i.e. N1 , N2, etc.), the geographical coordinates in the map and hence the position in the actual environment, where the coordinates may be x,y, z coordinates and has also been given in three dimensions according to the example. According to embodiments of the invention it is

contemplated that the map instead of being a 3D map is a 2D map and hence comprising e.g. only x,y coordinates. Any other kind of coordinate system may also be utilized, such as a polar coordinate system etc. The map data structure 400 further comprises information of neighboring nodes for each node. For example, node N1 of fig. 4 only has node N2 as neighbor, whereas node N3 has nodes N2,

N4, N5 as neighbors. This data structure representation thereby makes it possible to represent the graph, and hence map, as a table stored in memory, thus enabling search algorithms to quickly lookup nodes and search for other information such as neighbor nodes.

With regard to the invention, the path, i.e. track, being undertaken by the object, in the present example the vehicle 100, is estimated and used in the pattern matching. The estimation of the track may be performed using a gyroscope and/or one or more acceleration sensors along with information regarding the speed of the vehiclel OO.

As was mentioned above, the invention may be implemented e.g. in a consumer device, such as a tablet or smartphone or other kind of consumer devices. Such devices oftentimes comprise a gyroscope and/or acceleration sensors, which may be used according to the invention to determine e.g. turning motions of the vehicle, where the speed and/or traveled distance of the vehicle is also taking into account when determining the track of the vehicle. The speed of the vehicle, and/or the traveled distance, may be obtained e.g. from any kind of standardized interface by means of which the consumer device may communicate with the control system of the vehicle. Data of this kind is in general directly available from e.g. a data bus of the control system of the vehicle and may be accessed e.g. through a standardized interface. Data from the gyroscope/acceleration sensors of the consumer device and the speed of the vehicle may then be utilized to estimate a track that has been undertaken by the vehicle.

Fig. 5 illustrates an example of the manner in which a track of the vehicle may be generated. For simplicity only two dimensions are shown, but the track may be generated in a similar manner for three dimensions. The speed of the vehicle, and/or travelled distance, is used to determine the extension of the track while a gyroscope and/or acceleration sensors determine the turning motions, which in turn are used to determine the direction of motion of the vehicle thereby giving rise to a graph representing the track where the graph may be represented by vectors as in fig. 5, each vector e.g. representing a sample in time as the vehicle progress through the mine. The vectors may be e.g. 2D or 3D vectors.

According to embodiments of the invention, the vehicle track may also be

transformed to a data structure, in a similar manner as with regard to the map of the environment. Each vector of fig. 5, or each predetermined travelled distance, e.g. a same distance as with regard to the inter nodal distance being used in the map representation, may be represented by a node in a similar manner as with regard to the map representation above. The track data structure may, however, be less complex due to the track of the vehicle always being represented by a line having a head representing the current position of the vehicle, and a tail representing the earliest recorded (still saved) position of the vehicle.

According to embodiments of the invention, the position of the vehicle 100 in the 3D map (or 2D map as the case may be), and hence mine, is determined using pattern matching using the two data structures, where hence one of the data structures represent the environment of the vehicle, and the other data structure represents the track, of the vehicle as the vehicle moves through the spatial road network forming part of the mine.

An exemplary method 600 for determining the position of the vehicle 100 will be exemplified with reference to fig. 6. The method according to fig. 6 may be arranged to be performed continuously, e.g. when the vehicle 100 is in motion and/or at predetermined intervals and/or according to any other suitable criteria.

The method starts in step 601 where it is determined whether the determination of the position using pattern matching is to be commenced. The start of the method in fig. 6 may be arranged to be carried out e.g. each time vehicle is started, or according to any other criteria according to which the position of the vehicle 100 in the mine 300 is to be determined, such as e.g. when the position of the vehicle is not known. According to the present example, it is assumed that the position of the vehicle 100 in the mine 300 is unknown. This may be the case, for example, the first time the vehicle 100 is taken into use in the mine, or when the vehicle 100 has been moved without its position being tracked, or when a predetermined period of time has lapsed since the last time the position of the vehicle was determined, and the accuracy of the lastly determined position therefore being considered to involve a high degree of uncertainty.

In step 602, therefore, a“good location” flag is set to false. This means that it is assumed that the location of the vehicle is not known with a desirable accuracy. The accuracy is in general referred to as matching error ME in the present application, and when the position of the vehicle is not known the matching error ME is undetermined and hence high, and the matching error may also be set to a predetermined high value when the method is initiated.

In step 603 an estimation of the vehicle track is commenced, where the track may be determined as has been described above. In step 604 it is determined whether the length of the vehicle track is sufficient to perform pattern matching. It is in general desirable that the vehicle track has at least a minimum predetermined length. In case the vehicle track is too short, a large number of hits of the possible position of the vehicle in the representation of the environment may be obtained, since shorter parts of the paths of the mine may exhibit similarities, hence possibly resulting in a number of false positives. The minimum length may reduce the possibilities of such false positives in the determination of the position.

If it is determined in step 604 that the length of the vehicle track is not sufficient, the method continues to step 605, where the position of the vehicle is determined from some other positioning method, i.e. a non-pattern matching method. This may, for example, be a determination of the position using e.g. a wireless network, such as a radio-based network, where the position of the vehicle may be determined from the positions of one or more radio transmitters (access points) within the coverage area of which the vehicle 100 is present. In case a plurality of radio transmitters are within reach from the vehicle triangulation may be used. This is oftentimes not the case with regard to mines, and the position may be determined in relation to e.g. one radio transmitter where hence the position will be only very roughly determined. In general with regard to mines the wireless network coverage may be sparse and the vehicle be within reach of only one or two radio transmitters at a time.

This method hence merely determines the position of the vehicle 100 to be in a spefic area of the mine, and thereby a method for determining the position that exhibits a very low accuracy. Still this can be used to provide an approximate position of the vehicle at least in terms of in which portion of the mine the vehicle is being present, and which may be communicated e.g. to a control center and/or other functions of the mine, step 606, e.g. to be forwarded to other vehicles being present in the mine. The position is also stored in the vehicle itself, such as in the consumer device and/or vehicle control system and may be displayed on a map of the environment. The method then returns to step 603 to again determine whether the calculated vehicle track has reached a sufficient length. For as long as this is not the case, the input from other positioning method has preference and the method again continues to step 605, while otherwise the method continues to step 607 when the vehicle track has reached a sufficient length.

In step 607 it is again determined whether the good location flag is set to true, i.e. whether the matching error ME is below a threshold thres. According to the present example, this is still not the case, and the method therefore continues to step 608 where a full pattern matching is performed. According to the present application, full pattern matching means that pattern matching is performed for all nodes within a determined portion of the representation of the environment, i.e. according to the present example a determined portion of the mine.

Fig. 10 illustrates an exemplary embodiment of a method 1000 for performing full pattern matching. In step 1001 it is determined whether data from a non-pattern matching positioning method is available. According to the present example, this is the case since the vehicle is within the coverage area of the radio access point 205. The method therefore continues to step 1005. In case no such data would be available, the method may continue to step 1002 where it may be determined whether there is any previous knowledge of the position of the vehicle. This may be the case e.g. if the matching error in incremental pattern matching (described below) no longer provides accurate measurements. In step 1003 it is determined whether such information is too old to be considered reliable. If data is considered reliable, the method continues directly to step 1006, whereas otherwise the method awaits, step 1004, for positioning data from some non-pattern matching positioning method prior to proceeding to step 1006, where such data may be received e.g. when the vehicle comes within the coverage area of an access point in the mine.

In step 1006 it is determined a node/position representing the position obtained from the non-pattern matching positioning system, and from this position a number of nodes for which pattern matching is to be performed is determined, step 1007. The illustrated map of the environment according to figs. 2-3 may be highly simplified, and the real life structure of e.g. a mine may be considerably more complicated and extend over large geographical areas where e.g. mines also may comprise a number of different vertical levels, where each level may have an extensive pattern of paths.

In reality, the complete data structure of the environment may therefore comprise a very large number of nodes. This means that pattern matching may take a

considerable time in case pattern matching needs to be performed for the full extent of the environment data structure. Also, different portions of the environment, such as different portions of the mine may exhibit large similarities, e.g. from one level of a mine to another, or in terms of straight stretches or curves having a similar radius. Such similarities may result in false positive pattern matches even in spite of the length of the vehicle track that in turn may result in a falsely determined position of the vehicle.

According to the invention, therefore, the non-pattern matching positioning method is used to delimit the portion of the representation of the environment for which pattern matching is to be performed. In this way, the number nodes for which the full pattern matching is performed may be substantially reduced. This may be performed by calculating which nodes e.g. are within a predetermined distance from the node considered to represent the position of the vehicle. This is illustrated in fig. 7, where it is assumed that the vehicle 100 is within reach of the radio transmitter / access point 205 shown in fig. 2, the position of which therefore being considered to represent the position of the vehicle. According to the present example, the nodes to be

contemplated in the full pattern matching may comprise the nodes considered to be within the coverage area of the radio transmitter 205. This is illustrated by a circle 701 , which hence encircles a number of the nodes, but not all nodes, of the representation 300 of the environment. It is to be understood that in real life usage the proportion of unselected nodes will in general be considerably larger than according to the present example, and in general much greater than the selected number of nodes. If two or more radio transmitters are used in the positioning, the number of nodes can be further reduced. The circle 701 may alternatively represent a predetermined distance from an assumed position of the vehicle that has been determined in any other suitable way. The non-pattern matching positioning method hence delimits the number of nodes for which pattern matching is to be performed, and pattern matching is then performed for these nodes. This may substantially reduce the computational requirements of performing pattern matching in addition to reducing the risk for false positives.

With regard to the actual pattern matching, the pattern matching algorithm tries to match the vehicle track to the map node graph. In order to do this, the coordinates of the samples of the vehicle track may be transformed so that the lastly obtained sample (i.e. the head of the vehicle track) is transformed to the coordinates of a node in the map node graph for which pattern matching is to be performed, where hence the node of the map data structure is evaluated as a possible position of the vehicle 100. Also, the coordinate system of the object track may need to be rotated in order to align the nodes with the map nodes in coordinate system of the map. This may oftentimes be the case since the coordinate system in which the vehicle track is determined may be rotated in relation to the coordinate system of the mine.

According to the present example, a matching error ME is determined for each possible node in which the head of the vehicle track, and hence the vehicle, may be present, i.e. each of the nodes within the circle 701 of fig. 7. This may be performed by calculating the distance between the centers, or edges, of the nodes of the object track data structure and the corresponding node centers/edges of the nodes of the representation of the environment along the path being evaluated as possible match. This is illustrated in fig. 8, where the head of the vehicle track has been positioned in node N16, and where a corresponding nodes T1 -T4 of the vehicle track are compared with nodes N12-N15, respectively, and where each pair of nodes (i.e. node of the representation and a corresponding node of the vehicle track, N15-T1 , N14-T2, etc.) will exhibit a difference, and by determining this difference an error in the position is determined. In principle, the vehicle track may comprise any number of nodes T1 , ... Tn, but the number of nodes may be configured to comprise a number that result from the desired maximum track length and the desired mutual distance between nodes of the vehicle track.

A matching error ME of the node (N16 according to the present example) is estimated, where the matching error ME represents all pairwise node comparisons, so that the matching error ME indicates an overall match of the vehicle track in relation to the geography (path) of the mine. The smaller the matching error ME, the better the match.

The pattern matching is then performed, e.g. recursively, by selecting new start nodes of the map data structure, where the vehicle track is matched with the possible trails/paths of the map data structure. This is performed for all nodes for which the pattern matching is to be performed, i.e. according to the present example, the nodes being encircled by circle 701 in fig. 7. Furthermore, the possible trails for which the pattern matching is to be performed is determined from the length of the vehicle track and the geography on the map. For example, when there are intersections, a plurality of different alternative trails may be necessary to test for a particular node of the map data structure.

This is illustrated in figs. 9A-E. Fig. 9A illustrates the vehicle track of fig. 8, and figs. 9B-E illustrates trails of the map with different starting nodes in the pattern matching, where the figure illustrates trails of selected starting nodes N15, N16, N17. According to the present example, the possible trains/tracks are determined in step 1008 and matching errors are then calculated in step 1009 for these tracks.

According to the present example, the trail with start node N16, fig. 9D, will result in the match providing the lowest matching error ME and hence being determined as the position of the vehicle 100. Furthermore, node N15 gives rise to two possible trails, fig. 9B and fig. 9C. This is because of the branching at node N12. As is realized, in case there are branches closely located to each other, or more than two branches extend from a single node, the possible number of trails of a single node may be larger.

The matching error ME may be determined in any suitable way, and preferably takes into account mutual differences between pairs of nodes of the map node graph and the vehicle track, respectively. That is, with regard to the example in fig. 8, the object track head TH is compared with the node N16. In this case the object track head is shown as being slightly offset with regard to the node N16 for reasons of illustration, but may be configured to fully corresponding position to N16, thereby giving zero or only a small contribution to the matching error. The object track node T1 is compared with map nodeN15, object track nodeT2 is compared with map node N14, etc.

Alternatively, intermediate interpolated positions of the object track may be compared with corresponding interpolated positions between map nodes. When the pattern matching has been performed for all possible trails of all nodes, the node of the trail exhibiting the lowest matching error ME will be deemed to be the most likely position of the vehicle, step 1010, and when a good pattern matching has been obtained, i.e. a pattern match having a matching error ME below a

predetermined threshold thres has been found, step 609, this node, such as node N16, may be set as a good determination of the position of the vehicle, so that thereby the good location mode may also be set to true, step 610, i.e. the position of the vehicle is now known with high accuracy, the position being communicated according the above, and the method returning to step 603.

With regard to the matching error ME, a non-limiting example of a method for estimating the matching error is use of log-likelihood errors, and an exemplary method for estimating the matching error is shown in the following.

Let e[n] define the error between the map node graph and the object track at the n th sample, e.g. one of the node pairs discussed above, such as T1/N15. Assuming that the error is normally distributed, then the Probability Density Function (PDF) is given by; where 0 \s the parameter vector (e.g. object coordinates and rotations). The variable s[h] is the standard deviation of the normally distributed error. Further assuming that the errors of the nodes are independent, the log-likelihood function for a track n=1 ,. .,L/, such as TFI-T4 in fig. 8, is given by: log L(0) = logp log(

According to the present example, the standard deviation of the error, s[h], is assumed to increase linearly with the age of the sample. This is used to compensate for sensor drift because older samples will have less weight in the log-likelihood (and thus matching error) estimation. The matching error ME may then be defined to be proportional to the negative log- likelihood function,

Loglike oc — logL(0), and

Matching error ME = Loglike = ån=i(log(a[n]) + ₂ ^ )·

However, any other suitable method may also be utilized to determine the matching error ME.

Further with reference to fig. 6, the next time the method reaches step 607, the good location flag will be true, and the method therefore follow the“yes” branch of step 607. According to the present example, in this case, two methods are performed in parallel. Firstly, instead of performing full pattern matching, i.e. performing pattern matching for all nodes of a portion of the map, pattern matching is instead performed for the next consecutive node of the map that the vehicle is expected to reach during travel. With regard to the present example, this would be node N17 of fig. 8. This method is denoted incremental pattern matching since pattern matching is performed for the next subsequent node, and hence only a single node. The incremental pattern matching is performed in step 61 1 , and exemplified in fig. 1 1.

In step 1101 the last obtained position from the pattern matching is identified, i.e. the position of node N16 according to the present example. In step 1 102 the identity of the closest node in the map data structure given the obtained position is calculated, i.e. node N16. In step 1 103 the next node that the vehicle is expected to pass during travel is identified, where this may be performed in a straightforward manner given the inter-node relations of the map data structure. Hence node N17 will be identified. In step 1104 the corresponding map trail that the vehicle will have traveled when reaching node N17 is calculated, and in step 1 105 a corresponding matching error is calculated. Finally, in step 1 106 the position of the vehicle is set to the node forming the head of the map trail.

In step 612 it is determined whether the matching error ME obtained from step 1 105 is below a threshold thres, where the threshold thres may be the threshold thres of step 609 and/or step 616 or a different threshold. If the matching error ME is below the threshold thres, the method continues to step 613 in which self-calibration of sensor signals is performed. This is discussed further below. Furthermore, as was stated, two methods are performed in parallel, and in step 614, in addition to performing the incremental pattern matching, a dead reckoning pattern matching is also being performed. The dead reckoning pattern matching is illustrated further in fig. 12 and simply adds distance traveled by the vehicle to a position (node) of the map in which the vehicle is/has been considered to be present.

In step 1201 of fig. 12, a node from the pattern matching history, which has been tagged as a good match, i.e. exhibiting a low matching error is identified. This may be a node of the vehicle track or a node of the map, and in step 1202 the map node corresponding to the node identified in step 1201 is identified. Neighbor nodes of this node in the map data structure are then searched for in step 1203. In this case nodes may be identified for both directions of travel from the node identified in step 1202, and in step 1204 possible map trails are calculated from the nodes resulting from the search in step 1203. Matching errors for the possible trails are then calculated in step 1205, where the measured vehicle track is compared with the possible trails determined in step 1204. The best match is then selected as position of the vehicle in step 1206.

Flence, according to dead reckoning, the head of the object track is not matched to a specific node in the map graph, but instead the dead reckoning utilizes a node that previously has been considered a good match, and the object track extends from this node along the path of the map being followed by the vehicle where the distance travelled is calculated using dead reckoning.

In general when pattern matching results in a match where the estimated matching error is sufficiently low, this location may be stored as anchor point for future dead reckoning pattern matchings. The parallel methods of incremental pattern matching and dead reckoning pattern matching may thereby perform the pattern matching from different nodes, where the start node of dead reckoning pattern matching may be updated each time the incremental pattern matching results in a match with sufficiently low matching error.

Dead reckoning may be useful, for example, in cases where incremental-pattern matching may tend to perform badly. Oftentimes mines and tunnels have paths of a shape that make pattern matching very suitable when estimating the vehicle track since such paths often are subject to irregular bends. In some cases, however, the paths are less optimal for pattern matching. Such situations may arise, for example, if the path being taken, and thereby the track of the object, is circular or forms a straight line where various positions may give the same pattern matching result. The results from the incremental pattern matching (or extended incremental pattern matching, see below) and the dead reckoning pattern matching may then be compared, and the resulting position from these methods that gives rise to the lowest matching error ME may then be used as the position of the vehicle, step 615.

Further with regard to the incremental pattern matching, situations may arise where the matching error ME starts to increase which renders the determination of the position less accurate. In such cases, in case the matching error ME exceeds a threshold thres, step 612, which may be the same or different from other thresholds being used, a depth-first search (DFS) algorithm can be used to select a sub set of nodes in the direction of travel of the vehicle, step 618. This method is denoted extended incremental pattern matching herein. The extended incremental pattern matching is similar to the incremental pattern matching of fig. 11 , however with some differences. In step 1 103 the possible nodes in the map data structure that may have a position corresponding to the object track head will be the next X nodes in both directions of travel, where X , i.e. the number of nodes chosen as potential start nodes may be configured to depend e.g. on the previously calculated matching error ME from the pattern matching. The higher the matching error, the more nodes may be chosen. This greater number of nodes will result in a greater number of possible tracks which then are evaluated. Hence, with regard to the present example, in case extended incremental pattern matching is performed, not only node N17 would be

contemplated but e.g. also at least node N18 and possibly node N19 and possibly also further non-disclosed nodes.

In case the matching error ME continues to increase even in spite of use of extended incremental pattern matching, or otherwise does not fulfill the requirements regarding the matching error ME threshold thres, step 616, the good location mode is again set to false, step 617, with the result that full pattern matching will be performed again when the method reaches step 607.

With regard to the pattern matching, the vehicle track may, as discussed, be rotated to better align with the coordinate system of the map. According to embodiments of the invention, a number of different rotation angles of the vehicle track may be used in the pattern matching. The vehicle track may thereby be matched a plurality of times for a single map node, each match being carried out using different angles of rotation of the vehicle track. The rotation providing the lowest matching error ME may then be considered to be the closest match. This rotation may be performed for all types of pattern matching.

According to embodiments of the invention, pattern matching can also be used to determine if the vehicle is reversing. This can be done by generating an alternative object track where the speed is set to negative. If that object track result in a lower ME, it can be assumed that the vehicle is reversing. The original object track can then be discarded and the alternative object track can be set to be used for future pattern matching. However, this procedure requires more CPU power and may be disabled e.g. if the vehicle speed is higher than a certain threshold value.

As was mentioned above, according to embodiments of the invention, the method is implemented in a consumer device such as a tablet. Such products, however, in general suffers from the drawback that relatively "cheap" gyroscopes and/or acceleration sensors exhibiting mediocre accuracy are utilized. Also, the delivered sensor signals from sensors of this kind are subjected to a sensor value drift that may be dependent on various things, such as time and temperature.

According to embodiments of the invention, therefore, the pattern matching algorithm comprises a self-calibration feature to test out and compensate for sensor drift. This is performed, according to the example of fig. 6, in step 613 when a good match in incremental pattern matching has been obtained. When incremental pattern matching gives a good match, i.e. a low matching error, this indicates that the position of the object has been accurately determined with a high probability, and thereby also the shape of the path that the object has travelled is known with a high probability. This information can then be used to estimate the sensor drift for use in self-calibration. The difference in the vehicle track in relation to the map may be considered a result of inaccuracies and/or drift in the sensor measurements. This difference can be used to estimate an error in the sensor signals, so that the received sensor signals can be calibrated using the estimated error. In this way errors caused by sensor accuracy and/or drift may be at least partially compensated for to thereby further increase the accuracy in a subsequent determination of the position of the vehicle 100.

As has been described above, embodiments of the invention exhibit various advantages. For example, non-pattern matching positioning methods may have poor accuracy, and cellular and wifi systems e.g. in tunnels and mines often only allow accuracies in the position of the vehicle of 50 meters or more. The pattern matching according to the invention may provide considerably higher accuracy (e.g. in the order of 10 meters or higher accuracy).

Embodiments of the invention are also beneficial for implementation in user devices such as consumer tablets and still provide accurate determination of the position even though such devices in general suffer from constrained processing power, and/or limited memory, and/or mediocre sensors. According to embodiments of the invention, the required computational power is also reduced through the use of the plurality of different methods of pattern matching in dependence of the current accuracy in the determination of the position. When the invention is implemented using a stand-alone solution being connected to the vehicle and uses an interface, such as an OBDII interface, in order to receive speed data, the vehicle speed information does not necessarily indicate whether the vehicle is moving in a forward or reverse direction. It may therefore be necessary to be able to determine the direction of motion of the vehicle.

This is because gyroscope and accelerometer sensor signals may be used to detect the direction of acceleration, to thereby e.g. allow detection of turning motions, but the sensor signals may not be of sufficient quality to allow that it may be

distinguished between a situation when a vehicle is braking and a situation where instead the vehicle is accelerating in a reverse direction. Therefore, in order to obtain a vehicle track that corresponds to the actual vehicle motions, input regarding the direction of motion is required.

In case the invention is integrated in the control system of the vehicle, this is in general not an issue, since in such cases the information may be easily obtained e.g. from information regarding the current gear of the gearbox of the vehicle, and/or through the use of parameters using which the gear ratio (vehicle speed compared to engine speed, where each gear in general has a gear ratio being different from all other gears, and where a reverse gear may have the highest gear ratio) may be determined.

According to embodiments of the invention, when the direction of motion of the vehicle is not known, this can be determined by performing incremental pattern matching for vehicle tracks taking both directions of travel into account. That is, vehicle tracks for both a forward direction of travel and a reverse direction of travel from a node may be used in pattern matching. With regard to the example of fig. 8 not only node N17 would be contemplated in a subsequent pattern matching but e.g. also a track returning to node N15. Such reverse direction of travel tracks may be arranged to be always performed, e.g. as an incremental pattern matching, or only in situations where it is found that the matching error in incremental pattern matching suddenly increases. According to embodiments of the invention, the reverse direction of travel is only contemplated when signals from gyroscope/acceleration sensors indicate a possible change in direction of travel, e.g. by changes in acceleration, and /or when the vehicle has been stopped and again set in motion.

Embodiments of the invention hence provides a method for determining the position of an object, which allows the position to be determined with high accuracy, where a non-pattern matching positioning method is used to reduce the computational requirements in the pattern matching. With regard to, for example, deployments of the invention in mines, these are often provided with a wireless network, where wifi and/or cellular access points may be present at 50-100 meters mutual distance. This is more than sufficient to allow < 10 meter positioning accuracy according to the present positioning solution, and the invention hence does not add requirements on existing infrastructure. The combination of positioning methods allows this accuracy to be obtained even when the 2D/3D map may be inaccurate, and the sensor data is being received from sensors having poor accuracy. There is hence no requirement to use perfect maps and perfect sensors. The vehicle track may also be arranged to have a maximum length so that older, and thereby less reliable, data is discarded as new data is added.

Finally, although the invention has principally been exemplified with reference to a mine, the invention is applicable for any kind of moving object in an environment in which the object is constrained to follow a defined network of paths, and the above applies analogously for such implementations. For example, the invention may be utilized in the determination of the position of objects such as vehicles in warehouses etc.