Context based path planning for vector navigation in hexagonal spatial maps

Patent metadata

Field	Value
Publication number	US-10948918-B2
Application number	US-201816190894-A
Country	US
Kind code	B2
Filing date	Nov 14, 2018
Priority date	Feb 23, 2018
Publication date	Mar 16, 2021
Grant date	Mar 16, 2021

Abstract

Path planning for a robot is a compute intensive task. For a dynamic environment this is more cumbersome where position and orientation of objects changes often. Embodiments of the present disclosure provide systems and methods for context based path planning for vector navigation in hexagonal spatial maps. A 2-D environment is represented into a hexagonal grid map that includes hexagonal grid cells, objects are identified based on a comparison of RGB value associated with contiguous cells. Candidate contexts are determined based on objects identified. The hexagonal grid map is rotated at various angles and compared with pre-defined map(s) to determine quantitative measure of similarity for contexts identification from the candidate contexts, based upon which a path is dynamically planned for easy and efficient vector navigation within the hexagonal grid map. The embodiments further enable generating paths for different contexts using navigable common object(s) identified between intersections of the different contexts.

First claim

What is claimed is:

1. A processor implemented method, comprising:
obtaining and representing a two-dimensional (2D) environment into a hexagonal grid map, wherein the hexagonal grid map comprises a plurality of hexagonal grid cells ( 202 );
identifying one or more objects based on a comparison of Red Green Blue (RGB) value associated with a plurality of two or more contiguous cells from the plurality of hexagonal grid cells, wherein the one or more objects are identified based on number of hexagonal centers and distance of center of each hexagonal grid cell from center of one or more hexagonal grid cells ( 204 );
identifying one or more candidate contexts based on a tuple created for the identified one or more objects ( 206 );
iteratively performing a comparison of the hexagonal grid map with one or more pre-stored hexagonal grid maps, wherein the hexagonal grid map is description and iteratively compared with the one or more pre-stored hexagonal grid maps obtained from a map database to determine a Spatial Similarity Quotient (SSQ), and wherein the Spatial Similarity Quotient is indicative of degree of overlap of the hexagonal grid map with at least one of the one or more pre-stored hexagonal grid maps ( 208 );
identifying one or more contexts from the one or more candidate contexts based on the determined spatial similarity quotient ( 210 ); and
dynamically planning a path for vector navigation within the hexagonal grid map based on the one or more objects, and the identified one or more contexts ( 212 ).

2. The processor implemented method of claim 1 , further comprising generating an object database for each of the one or more objects based on an annotation, side of bounding square, a template shape, and a variance in the RGB value.

3. The processor implemented method of claim 1 , further comprising generating a context database for each of the one or more probable contexts with the identified one or more objects in a tuple.

4. The processor implemented method of claim 1 , wherein the one or more objects are identified as one or more predefined objects when the RGB value of the one or more objects is equal to a predefined threshold.

5. The processor implemented method of claim 1 , wherein the one or more objects are determined as new objects when the RGB value of the one or more objects is greater than or less than a predefined threshold.

6. The processor implemented method of claim 1 , wherein size and shape of the one or more objects are determined based on the distance.

7. The processor implemented method of claim 1 , further comprising
identifying one or more common objects that indicate an intersection of two or more contexts; and
generating a path based on one or more navigable objects identified from the one or more common objects from the intersection of the two or more contexts.

8. The processor implemented method of claim 1 , wherein the one or more contexts and the one or more objects are identified using information obtained from one or more sensors.

9. The processor implemented method of claim 1 , further comprising
training a robot using the dynamically planned path, the one or more contexts and the one or more objects identified for subsequent path planning and vector navigation; and
generating a database comprising information pertaining to the subsequent path planning and vector navigation.

10. The processor implemented method of claim 1 , further comprising:
performing a comparison of the hexagonal grid map with the one or more candidate contexts to obtain a maximum SSQ; and
identifying an environment as a new environment or a pre-defined environment based on the comparison of the maximum SSQ with a pre-defined threshold.

11. A system ( 100 ), comprising:
a memory ( 102 ) storing instructions;
one or more communication interfaces ( 106 ); and
one or more hardware processors ( 104 ) coupled to the memory ( 102 ) via the one or more communication interfaces ( 106 ), wherein the one or more hardware processors ( 104 ) are configured by the instructions to:
obtain and represent a two-dimensional (2D) environment into a hexagonal grid map, wherein the hexagonal grid map comprises a plurality of hexagonal grid cells;
identify one or more objects based on a comparison of Red Green Blue (RGB) value associated with a plurality of two or more contiguous cells from the plurality of hexagonal grid cells, wherein the one or more objects are identified based on number of hexagonal centers and distance of center of each hexagonal grid cell from center of one or more hexagonal grid cells;
identify one or more candidate contexts based on a tuple created for the identified one or more objects;
iteratively perform a comparison of the hexagonal grid map with one or more pre-stored hexagonal grid maps, wherein the hexagonal grid map is transformed to one or more variations and iteratively compared with the one or more pre-stored hexagonal grid maps obtained from a map database to determine a Spatial Similarity Quotient (SSQ), wherein the Spatial Similarity Quotient is indicative of degree of overlap of the hexagonal grid map with at least one of the one or more pre-stored hexagonal grid maps;
identify one or more contexts from the one or more candidate contexts based on the determined spatial similarity quotient; and
dynamically plan a path for vector navigation within the hexagonal grid map based on the one or more objects, and the identified one or more contexts.

12. The system of claim 11 , wherein the one or more hardware processors are further configured by the instructions to generate an object database for each of the one or more objects based on an annotation, side of bounding square, a template shape, and a variance in the RGB value.

13. The system of claim 11 , wherein the one or more hardware processors are further configured by the instructions to generate a context database for each of the one or more probable contexts with the identified one or more objects in a tuple.

14. The system of claim 11 , wherein the one or more objects are identified as one or more predefined objects when the RGB value of the one or more objects is equal to a predefined threshold.

15. The system of claim 11 , wherein the one or more objects are determined as new objects when the RGB value of the one or more objects is greater than or less than a predefined threshold.

16. The system of claim 11 , wherein size and shape of the one or more objects are determined based on the distance.

17. The system of claim 11 , wherein the one or more hardware processors are further configured by the instructions to:
identify one or more common objects that indicate an intersection of two or more contexts; and
generate a path based on one or more navigable objects identified from the one or more common objects from the intersection of the two or more contexts.

18. The system of claim 11 , wherein the one or more contexts and the one or more objects are identified using information obtained from one or more sensors.

19. The system of claim 11 , wherein the one or more hardware processors are further configured by the instructions to:
train a robot using the dynamically planned path, the one or more contexts and the one or more objects identified for subsequent path planning and vector navigation; and
generate a database comprising information pertaining to the subsequent path planning and vector navigation.

20. The system of claim 11 , wherein the one or more hardware processors are further configured by the instr

Assignees

• Tata Consultancy Services Ltd

Inventors

• Dey Sounak
• Mukherjee Arijit
• Sarkar Aritra

Classifications

• G01C21/206 Primary

  specially adapted for indoor navigation · CPC title

• G01C21/3881

  Tile-based structures · CPC title

• G01C21/20

  Instruments for performing navigational calculations (G01C21/24, G01C21/26 take precedence) · CPC title

• G01C21/005

  with correlation of navigation data from several sources, e.g. map or contour matching (G01C21/30 takes precedence) · CPC title

• G01C21/3415

  Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents · CPC title