The various embodiments herein provide a system and method to determine a refined absolute position and a refined absolute orientation of an entity in a navigation space in a cost-effective manner along with good accuracy while eliminating any dependency on any dynamically changing scenario or unplanned changes in the navigation space. With no reference to historical data, quality of the absolute position and orientation remains the same and does not degrade during any interval of time due to dependency on recency of old data.

According to one embodiment herein, a system for determining a refined absolute position and a refined absolute orientation of an entity in a navigation space is disclosed. According to an embodiment of the present invention, the system includes a plurality of sensors including a first set of sensors disposed on a first plurality of locations on the entity, wherein the first set of sensors are part of a cartesian coordinate system provided by a local positioning system formed using a technology such as, but not limited to, UWB, Bluetooth, Zig-bee, Ultrasound, others. According to another embodiment of the present invention, second set of sensors disposed on a second plurality of locations on the entity. The system also includes a coarse absolute position and orientation estimation unit configured to determine at least one of: a coarse absolute position and a coarse absolute orientation, of the entity based on a position data captured in a two-dimensional cartesian plane of the cartesian coordinate system at predetermined frequency/interval by the first set of sensors. The system further includes a relative position and orientation estimation unit configured to determine at least one of: a relative position and a relative orientation, of the entity relative to the predetermined path based on a set of data captured at a predetermined frequency/interval from the second set of diversified sensors. The system further includes a navigation guidance unit configured to provide unique attributes based on a desired navigable layout identified in the indoor navigation space and to update one or more of the attributes dynamically as a learning/feedback based on a historical navigation data. The system further includes an analytics unit configured to determine at least one of a refined absolute position and a refined absolute orientation of the entity at a predetermined frequency/interval by fine tuning: the coarse absolute position and the coarse absolute orientation based on 1) one or more of the plurality of inputs provided by the relative position and orientation estimation unit, 2) coarse absolute position of the entity and 3) the unique attributes provided by the navigation guidance unit.

According to one embodiment herein, the analytics unit is configured to transform the predetermined path by rotating a navigation plane associated with the predetermined path by a rotation angle to align the predetermined path to become parallel to X-axis or Y-axis in the two-dimensional cartesian plane and to generate a transformed navigation plane, and wherein the coarse absolute position is also rotated through the same rotation angle to obtain a transformed coarse absolute position of the entity, and wherein by modifying/correcting the transformed coarse absolute position of the entity, based on one or more of the plurality of inputs from the relative position and orientation estimation unit, a transformed refined absolute position of the entity is obtained, and wherein the transformed coarse absolute position of the entity is corrected/modified by substituting a combination of a transformed ideal coordinate value of interest and one or more of the plurality of inputs from the relative position and orientation estimation unit, to either X or Y value of the transformed coarse absolute position coordinates of the entity depending up on the rotation applied during transformation of the plane, and wherein the transformed ideal coordinate value of interest is equal to a transformed ideal starting point coordinate value selected based on the transformation applied, and wherein the ideal starting point coordinate is the coordinate of the starting node in the line segment obtained from the navigation map, and wherein the refined absolute position of the entity is obtained by rotating back the navigation plane in the reverse direction, through the same rotation angle, to the original orientation of the navigation plane, and wherein the transformed refined absolute position rotates by the same angle to provide the refined absolute position of the entity.

According to one embodiment herein, the refined absolute orientation of the entity is derived based on 1) the relative orientation of the entity obtained from the relative position and orientation estimation unit and 2) the coarse absolute orientation obtained from the coarse absolute position and orientation estimation unit, wherein in the transformed navigation plane the relative position and orientation estimation unit provides the relative orientation of the entity with respect to the transformed path which is either parallel to one of X-axis or Y-axis based on the transformation applied, wherein as the absolute orientation of the transformed path is the same as one of X-axis or Y-axis, a transformed absolute orientation of the entity in the transformed navigation plane is derived by adding the relative orientation of the entity along with its sign to the absolute orientation of the transformed path, wherein by rotating the transformed navigation plane in the reverse direction by the same quantity as the rotation angle, the transformed absolute orientation angle undergoes similar rotation and provides an interim representation of the absolute orientation of the entity, wherein the refined absolute orientation of the entity is obtained as a weighted combination of the coarse absolute orientation and the interim representation of the absolute orientation of the entity.

According to one embodiment herein, the analytics unit is configured to select and use one or more of the relative positions and the relative orientations from the relative position and orientation estimation unit from among a plurality of inputs. Such plurality of inputs to the analytics unit is derived by the relative position and orientation estimation unit using the diversified set of sensors among the second set of sensors. The choice of the specific inputs to be used is guided by the navigation map based on the coarse absolute position.

According to one embodiment herein, the analytics unit is configured to seamlessly select and use one or more of the relative positions and the relative orientations from the relative position and orientation estimation unit from among a plurality of inputs while navigating through different sections of a navigation layout involving either a plurality of line segments or a single line segment with varying physical attributes, wherein the selection is guided by the navigation map based on the coarse absolute position of the entity wherein the navigation map provides the physical attributes associated with each such line segment like, for example but not limited to, a wall adjacent to the navigation path along with its side, presence of lane marking and others.

According to one embodiment herein, the first plurality of locations on the entity comprises a front end and a rear end of the entity and the second plurality of locations comprises at least one of: a left side of the entity, a right side of the entity, a front end of the entity, and a back end of the entity.

According to one embodiment herein, a method of navigating an entity along a predetermined path in a navigation space is disclosed. The method includes 1) initiating navigation of the entity along the predetermined path in the navigation space, 2) determining at least one of: a coarse absolute position and a coarse orientation of the entity based on a position data captured at predetermined frequency/interval by a first set of sensors from among a plurality of sensors, disposed on a first plurality of locations on the entity, 3) determining at least one of: a relative position and a relative orientation, of the entity with respect to the predetermined path based on a set of data captured from a second set of diversified sensors from among the plurality of sensors, disposed on a second plurality of locations on the entity, 4) selecting at least one of: a relative position and relative orientation of the entity with respect to the predetermined path from among the plurality of relative position and relative orientation based on the coarse absolute position and a navigation map 5) determining a refined absolute position and a refined absolute orientation of the entity by fine tuning: the coarse absolute position based on relative position and the coarse absolute orientation based on relative orientation, using the navigation map, wherein the instantaneous map is generated based on a map data and a machine learning model based on a historical navigation data. 6) Continuing steps 2 to 5 until the destination is reached.

The various embodiments disclosed herein provide a method and a system for determining a refined absolute position and orientation of an entity in a navigation space is provided. The system and method disclosed herein determine a refined absolute position and a refined absolute orientation of an entity in a navigation space based on extraction of diversified features in the navigation space using diversified sensors used to seamlessly help improve accuracy of absolute position including on-the-fly switchovers. Also, the system and method disclosed herein achieves accurate absolute position using coarse absolute position and a unique combination of relative positions extracted from diversified sensors using specific features in the navigation space. The entity can include a stationary object or a mobile object.

FIG. 1 illustrates a block diagram of a system for determining a position and an orientation of an entity in a navigation space, according to one embodiment herein. As depicted in FIG. 1, the system 102 includes a plurality of sensors 104, a coarse absolute position and orientation estimation unit 106, a relative position and orientation estimation unit 108, a navigation guidance unit 110, and an analytics unit 112. The entity may include for example, a stationary object or a mobile object (such as for example, a mobile factory equipment or vehicle). The navigation space includes an enclosed space or an open space with predefined boundaries, such as for example, a space inside a factory unit. According to one embodiment herein, the plurality of sensors includes a first set of sensors disposed on a first plurality of locations on the entity and a second set of sensors disposed on a second plurality of locations on the entity. The second plurality of sensors may include, for example, but not limited to, proximity sensing devices, image capture devices etc.

According to one embodiment herein, the coarse absolute position and orientation estimation unit 106 is configured to determine at least one of: a coarse absolute position and a coarse absolute orientation, of the entity based on a position data captured at predetermined frequency/interval by the first set of sensors (explained further along with FIGS. 2A-2B). The predetermined path includes an ideal navigation path for the entity within the navigation space. According to one embodiment herein, the relative position and orientation estimation unit 108 is configured to determine at least one of: a relative position and a relative orientation, of the entity relative to the predetermined path based on a set of data captured at predetermined frequency/interval from the second set of diversified sensors (explained further along with FIGS. 3A-3C).

According to one embodiment herein, the navigation guidance unit 110 is configured to provide unique attributes based on a desired navigable layout identified in the indoor navigation space and to update one or more of the attributes dynamically as a learning/feedback based on a historical navigation data. According to one embodiment herein, the navigation guidance unit 110 includes a centralized/local system or a device that contains unique pre-defined attributes for every line segment of a virtual map created for the navigation space (e.g. factory floor). The unique pre-defined attributes include, but is not limited to nodes, destination points, absolute coordinates of nodes and other attributes, valid paths connecting each node with every other node, an optimal route between nodes, an associated cost and intermediate transition angles, an augmentation for each line segment such as an ideal path for the segment, presence/usability of a wall on either side of the passage with sub-section granularity capturing possible gaps when wall is not present, presence of lane lines on either side of the line segment, a lane width, a maximum speed to travel based on lane width and any other consideration, an orientation angle offset at each node and the like.

According to one embodiment herein, the navigation guidance unit 110, generates an initial map using initial set of input data such as for example node coordinates, valid paths, path width, and the like. The initial set of input data is processed to arrive at a robust map in a unique way that pretty much has every attribute required to perform successful navigation from the very first run without any specific training need for the entity 200. For subsequent refinements/dynamic update of attributes like node orientation angle offset, presence of a wall or fixed structure along path, reliability of a lane marking on the floor for a given segment and the like. The navigation guidance unit 110, gathers/collects various data from the entity during navigation and applies machine learning (ML) techniques for further inference. According to an embodiment of the present invention, the dynamic map generation unit 110, uses the data inferred based on ML collected based on the experience of various entities and further applies artificial intelligence techniques and refines the attributes updates the initial map. Subsequently, the updated map is made available from very next navigation for all entities in the navigation space.

According to one embodiment herein—the analytics unit 112 is configured to determine at least one of a refined absolute position and a refined absolute orientation of the entity at a predetermined frequency/interval by fine tuning: the coarse absolute position and the coarse absolute orientation based on 1) one or more of the plurality of inputs provided by the relative position and orientation estimation unit (108), 2) coarse absolute position of the entity and 3) unique attributes provided by the navigation guidance unit (110). According to one embodiment herein, the analytics unit 112 is configured to transform the predetermined path 304 by rotating a navigation plane 402 associated with the predetermined path by a rotation angle so as to align the predetermined path parallel to one of X-axis or Y-axis of the two-dimensional cartesian plane to generate a transformed navigation plane 404 wherein the coarse absolute position as well undergoing the same rotation to become transformed coarse absolute position of the entity. According to one embodiment herein, the analytics unit 112 is configured to apply a refinement to the transformed absolute position based on one or more of the plurality of inputs from the relative position and orientation estimation unit to obtain a transformed refined absolute position of the entity on the transformed navigation, wherein the refinement is a simple substitution of a combination of a transformed ideal coordinate value of interest and one or more of the plurality of deviations from the predetermined path from among the plurality of inputs from the relative position and orientation estimation unit, to either X or Y value of the transformed coarse absolute position coordinates of the entity depending up on the rotation applied during transformation of the plane, wherein the transformed ideal coordinate value of interest is the same as one of the transformed ideal starting point coordinate values selected based on the transformation applied, wherein the ideal starting point is the theoretical coordinates for the starting node in the line segment obtained from the navigation map. According to one embodiment herein, the analytics unit 112 is configured to obtain a refined absolute position of the entity by rotating the navigation plane in the reverse direction by same quantity as the rotation angle back to the original orientation of the navigation plane 402, wherein the transformed refined absolute position rotates by the same angle to provide the refined absolute position of the entity. (explained further along with FIGS. 4A-4B).

According to one embodiment herein, the analytics unit 112 derives the refined absolute orientation of the entity based on 1) the relative orientation of the entity obtained from the relative position and orientation estimation unit 108 and 2) the coarse absolute orientation obtained from the coarse absolute position and orientation estimation unit 106, wherein in the transformed navigation plane the relative position and orientation estimation unit 108 provides the relative orientation of the entity with respect to the transformed path which is either parallel to one of X-axis or Y-axis based on the transformation applied, wherein as the absolute orientation of the transformed path is the same as one of X-axis or Y-axis, a transformed absolute orientation of the entity in the transformed navigation plane is derived by adding the relative orientation of the entity along with its sign to the absolute orientation of the transformed path, wherein by rotating the transformed navigation plane 404 in the reverse direction by the same quantity as the rotation angle, the transformed absolute orientation angle undergoes similar rotation and provides an interim representation of the absolute orientation of the entity, wherein the refined absolute orientation of the entity is obtained as a weighted combination of the coarse absolute orientation and the interim representation of the absolute orientation of the entity. (explained further along with FIGS. 3C, 4A-4B and 8). According to an embodiment of the present invention, the analytics unit 112 is configured to select and use one or more of the relative positions and the relative orientations from the relative position and orientation estimation unit 108 from among a plurality of inputs, wherein such plurality of inputs to the analytics unit 112 is derived by the relative position and orientation estimation unit 108 using the diversified set of sensors among the second set of sensors. The choice of the specific inputs to be used is guided by the navigation map based on the coarse absolute position. According to one embodiment herein, the analytics unit 112 is configured to seamlessly select and use one or more of the relative position and the relative orientation from among the plurality of inputs while navigating through different sections of a navigation layout involving either a plurality of line segments or a single line segment with varying physical attributes, wherein the selection is guided by the navigation map based on the coarse absolute position of the entity wherein the navigation map provides the physical attributes associated with each such line segment like, for example but not limited to, a wall adjacent to the navigation path along with its side, presence of lane marking and others (explained further along with FIG. 6).

FIGS. 2A-2B exemplarily illustrates positioning of the first set of sensors at the first plurality of locations on an example entity, according to one embodiment herein. As depicted in FIG. 2A the example entity 200 includes a front end 206 and a rear end 204. The first set of sensors 202A-H includes a rear set of sensors 202E-H disposed on the rear end 204 and a front set of sensors 202 A-D disposed on the front end 206, of the example entity 102. FIG. 2B depicts a representation of positioning of the first set of sensors 202A-H on the example entity 200 in an X-Y plane 208. As depicted in FIG. 2B the points B1 to B4 and the points F1 to F4 represent the positioning of the sensors 202E-H and 202A-D respectively. The first set of sensors 202A-H are positioned in a manner to achieve a three-dimensional spatial diversity. The first set of sensors 202A-H capture an absolute position of the example entity and the absolute position provided by each sensor is used to calculate a redundant set of absolute orientation representations and an average of the absolute orientation representations is used to determine an absolute orientation of the entity in the XY plane 208.

According to one embodiment herein, the position of the entity (such as example entity 200) as captured by the first plurality of sensors (such as the first plurality of sensors 202A-H) is used to determine at least one of a coarse absolute position and/or a coarse absolute orientation. According to one embodiment herein, the coarse absolute position and orientation estimation unit 106 determines of the lines B1F1 212 & B4F4 214 as depicted in FIG. 2B. The lines B1F1 212 & B4F4 214, from back to front provide a representation of the angle that the entity is facing at any given instance with respect to the predetermined path. The coarse absolute position and orientation estimation unit 106 determines the angle of the lines B1B4 216 and F1F4 218. The lines B1B4 216 and F1F4 218 provide an angle that is 90 degrees higher than the angle of the entity. The absolute position unit 106 combines the angles to get a Quad_Sensor_Angle. The Quad_Sensor_Angle is given by equation (1):

Quad_Sensor_Angle=((∠B1F1+∠B4F4+(∠B1B4−90)+(∠F1F4−90))/4 2 (1)

According to one embodiment herein, the coarse absolute position and orientation estimation unit 106 determines a first centre point (BC) using the points B1B2B3B4. The BC is given by equation (2):

BC=(B1+B2+B3+B4)/4 (2)

According to one embodiment herein, the coarse absolute position and orientation estimation unit 106 determines a second centre point (FC) using the points B1B2B3B4. FC is given by equation (3):

FC=(F1+F2+F3+F4)/4 (3)

The coarse absolute position and orientation estimation unit 106 determines an angle (Centre_Of_Sensors_Angle) representing the line BCFC given by equation (3):

Centre_Of_Sensors_Angle=∠BCFC (4)

According to one embodiment herein, the coarse absolute position and orientation estimation unit 106 determines an angle representing the line B1F4 and an angle representing the line B4F1. Although the lines B1F4 and B4F1 have an offset with respect to the orientation of the entity, as the first set of sensors 202A-H are positioned in a rectangular fashion, the offset gets negated. For example, as depicted in FIG. 2B an actual orientation of the entity is 270 degrees. Suppose B1F4 is at an angle 300 degrees, then B4F1 would be at 240 degrees. Accordingly, a sum of the angle of B1F4 and angle of B4F1 gives a representation of instantaneous orientation (Big_Diagonal_Angle) of the entity given by equation (5):

Big_Diagonal_Angle=(∠B1F4+∠B4F1)/2 (5)

According to one embodiment herein, the coarse absolute position and orientation estimation unit 106 determines uses the points BC and FC identified in Centre_Of_Sensors_Angle. The coarse absolute position and orientation estimation unit 106 determines angles representing BCF1 & BCF4 and determines an average of the angles to obtain an angle SD_Angle_1. The coarse absolute position and orientation estimation unit 106 determines angles representing B1FC & B4FC and an average of the angles to get an angle SD_Angle_2. The coarse absolute position and orientation estimation unit 106 determines a Small_Diagonal_Angle by averaging SD_Angle_1 and SD_Angle_2 given by equation (6):

Small_Diagonal_Angle=((∠BCF1+∠BCF4)/2+(∠B1FC+∠B4FC)/2)/2 (6)

According to one embodiment herein, the coarse absolute position and orientation estimation unit 106 determines a coarse absolute orientation of the entity given by equation (7):

coarse absolute orientation=(K1*Quad_Sensor_Angle+K2*Centre_Of_Sensors_Angle+K3*Big_Diagonal_Angle+K4*Small_Diagonal_Angle)/(K1+K2+K3+K4) (7)

where K1, K2, K3 and K4 are multiplication constants arrived based on a confidence level of each angle representation.

FIGS. 3A-3B exemplarily illustrates positioning of second set of sensors at the second plurality of locations on an example entity, according to one embodiment herein. As depicted in FIG. 3A the second set of sensors 302A-C are positioned along a left-side surface 304 of the example entity 200. The second set of sensors 302A-C can also be positioned along a right-side surface of the example entity 200 (not shown). The second set of sensors 302A-C provide a measure of a distance (d) of the entity from side walls or a fixed structure located on a side of a pathway.

The relative position and orientation estimation unit 108 determines a deviation from the predetermined path (ideal navigation path) based on the distance (d) as explained further along with FIG. 3B. FIG. 3B illustrates a process of determining a deviation of the entity from the predetermined path during navigation in the navigation space, in accordance with an embodiment. As depicted in FIG. 3B, a width of the entity 200 is represented by “b” 306, a distance of the entity 200 from a left side wall 310 is represented by “d” 308. The relative position and orientation estimation unit 108 determines the deviation (Δw) 312 given by equation (8):

Δw=w/2−(d+b/2) (8)

- where w/2 represents a distance between the left wall 310 and the predetermined path 304 and a distance between the predetermined bath and an assembly line-1 314 or assembly line-2 316 in a navigation space.

According to one embodiment herein, the relative position and orientation estimation unit 108 is configured to determine a relative position and/or a relative orientation of the entity 200 based on a sensor (for example, an image capturing device) from among the second set of sensors, positioned in front, back, and/or middle of the entity 200 by determining a relative position of the entity 200 inside a marked passage like a lane as depicted in FIG. 3C. Sensors 306A and 306B placed on the front side 206 and the rear side 204 respectively as shown in FIG. 3A represent one such embodiment.

FIG. 3C exemplarily illustrates determining the relative position and relative orientation of the entity 200, according to one embodiment herein. More particularly, FIG. 3C depicts a front perspective view of the entity 200 with a sensor (image capture device) 320 positioned on the front side of the entity 200. The entity navigates along the predetermined path 304. The sensor 320 captures the distance of the entity 200 relative to a pair of lane lines 322 and 324. The relative position and orientation estimation unit 108 determines a deviation Aw of the entity 200 from the predetermined path (or ideal path) 304 based on a distance from the middle of the entity (where sensor or image capture device is placed). The deviation Aw of the entity 200 is determined based on equation (8). Also, the difference in the angle of the lane lines as perceived by the sensor 320 enables the relative position and orientation estimation unit 108 to determine the relative orientation of the entity with respect to the lane lines.

According to one embodiment herein, the relative position and orientation estimation unit 108 determines the relative position and relative orientation of the entity 200 using a system that provides the depth information of the predetermined path 304. Using the depth information, the relative position and orientation estimation unit 108 draws virtual lanes and then the deviation from the predetermined path 304 is identified as explained along with FIGS. 3B-3C.

FIGS. 4A-4B depicts a transformation of a navigation plane 402 to align the predetermined path with Y-axis always as shown in the transformed navigation plane 404, according to one embodiment herein, wherein the coarse absolute position transforms to become transformed coarse absolute position of the entity. A floor alignment similar to FIG. 3B requires a simple step to augment a deviation of the entity 200 from the predetermined path, by refining only the Y value among the XY coordinates determined based on the transformed coarse absolute position. For a generic solution that eliminates the constraint on factory floor alignment with XY axes, the analytics unit 112 transforms the predetermined pathway (line segment) by means of plane rotation so as to always align it parallel to one of the axes, such as for example, Y axis. As depicted in FIG. 4A, if (x,y) is an absolute set of coordinates of the entity 200 provided by the coarse absolute position and orientation estimation unit 106, the analytics unit 112 rotates an initial plane 402 by Θ (angle between the direction of the entity and the Y-axis) to obtain a transformed plane 404 parallel to the Y axis, the transformed coordinates of the entity 200 in a transformed plane 404 would be (x_t, y_t), where x_tis given by equation (9):

x_t=x*cos(Θ)+y*sin(Θ); y_t=−x*sin(Θ)+y*cos(Θ) (9)

As deviation from the predetermined (ideal) path in the transformed plane 404 is a simple refinement only to x_t, the analytics unit 112 applies the refinement based on the instantaneous relative position of the entity 200 received from the relative position and orientation estimation unit 108 to get the coordinates (x′_t, y_t). Given, (x_i, y_i) the start coordinates in the predetermined path, the transformed x, value x_i^tis given by equation (10):

xⁱ_t=xⁱ*cos(Θ)+yⁱ*sin(Θ) (10)

After transformation, the predetermined (ideal) path would be parallel to the Y-axis and all values in the predetermined path will have same value x