# US 10,768,011 B2 · Method and system for positioning an autonomous vehicle on a navigation map > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,768,011 B2 - Document ID: US10768011B2 - Status: Granted - Kind: B2 - Application number: 15/787,784 - Filed: 2017-10-19 - Published: 2019-02-28 - Granted: 2020-09-08 - Earliest claimed: 2017-08-31 - Assignees: Wipro Limited - Applicants: Wipro Limited - Inventors: Balaji Sunil Kumar; Manas Sarkar; Shyam Sundar Pal - Web page: https://patentgrep.com/patent/US10768011B2 ## CPC - G01C 21/367: {Details, e.g. road map scale, orientation, zooming, illumination, level of detail, scrolling of road map or positioning of current position marker} - G01C 21/30: Map- or contour-matching - G01S 19/485: {whereby the further system is an optical system or imaging system} - G01S 19/49: whereby the further system is an inertial position system, e.g. loosely-coupled - G05D 1/024: {in combination with a laser (lasers per se H01S)} - G05D 1/027: {comprising intertial navigation means, e.g. azimuth detector (inertial navigation G01C21/16; inertial navigation combined with non-inertial navigation instruments G01C21/165)} - G05D 1/0274: {using mapping information stored in a memory device (navigation using map-matching G01C21/30)} - G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S) - G01S: RADIO DIRECTION-FINDING; RADIO NAVIGATION; DETERMINING DISTANCE OR VELOCITY BY USE OF RADIO WAVES; LOCATING OR PRESENCE-DETECTING BY USE OF THE REFLECTION OR RERADIATION OF RADIO WAVES; ANALOGOUS ARRANGEMENTS USING OTHER WAVES - G05D: SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES ## Abstract Disclosed herein are a method and system for positioning an autonomous vehicle on a navigation map. The method includes positioning the autonomous vehicle on the navigation map, including receiving the navigation map, an approximate position and an approximate orientation of the autonomous vehicle on the navigation map, and an environmental field of view (FOV) of the autonomous vehicle and determining a first road boundary based on the navigation map and the approximate position of the autonomous vehicle, and a second road boundary based on the environmental FOV and the approximate orientation of the autonomous vehicle, further determining at least one of an angular deviation and a lateral deviation between the first road boundary and the second road boundary, and positioning the autonomous vehicle on the navigation map by minimizing at least one the angular deviation and the lateral deviation. ## Claims ### Claim 1 A method for positioning an autonomous vehicle on a navigation map, the method comprising: receiving, by a navigation device, the navigation map, an approximate position and an approximate orientation of the autonomous vehicle on the navigation map, and an environmental field of view (FOV) of the autonomous vehicle; determining, by the navigation device, a first road boundary based on the navigation map and the approximate position of the autonomous vehicle, and a second road boundary based on the environmental FOV and the approximate orientation of the autonomous vehicle; determining, by the navigation device, at least one of an angular deviation and a lateral deviation between the first road boundary and the second road boundary; and positioning, by the navigation device, the autonomous vehicle on the navigation map by minimizing at least one the angular deviation and the lateral deviation, based on a plurality of maneuverability sequences, wherein the autonomous vehicle is positioned based on command velocities generated for each of the plurality of maneuverability sequences, and wherein a maneuverability sequence from the plurality of maneuverability sequences comprises a trajectory along two arms of a right angle triangle, and wherein a first portion of the trajectory comprises a forward motion along an arm of the triangle opposite to the right angle, and a second portion of the trajectory comprises a reverse motion along an arm adjacent to the right angle of the triangle. ### Claim 2 (depends on 1) The method of claim 1, wherein the navigation map is a pre-generated light detection and ranging (LIDAR) map, wherein the approximate position of the autonomous vehicle is received from a GPS sensor, wherein the approximate orientation of the autonomous vehicle is received from an inertia measurement unit (IMU), and wherein the environmental FOV is received from a LIDAR scanner. ### Claim 3 (depends on 1) The method of claim 1, wherein determining the first road boundary comprises determining a pre-identified road boundary from the navigation map in a direction of movement of the autonomous vehicle, and wherein the direction of movement is determined based on the approximate position of the autonomous vehicle. ### Claim 4 (depends on 1) The method of claim 1, wherein determining the second road boundary comprises determining a road boundary from the environmental FOV with respect to the approximate orientation of the autonomous vehicle. ### Claim 5 (depends on 1) The method of claim 1, wherein determining the second road boundary comprises: determining a region in the environmental FOV in a vicinity of at least a portion of the first road boundary; determining a plurality of data points ordered in a straight line within the region and with respect to the approximate orientation of the autonomous vehicle; and determining a road boundary based one the plurality of data points. ### Claim 6 (depends on 1) The method of claim 1, wherein determining the angular deviation comprises determining an angle and an angular direction between the first road boundary and the second road boundary. ### Claim 7 (depends on 6) The method of claim 6, wherein positioning the autonomous vehicle by minimizing the angular deviation comprises aligning the autonomous vehicle in parallel to the first road boundary in the plurality of maneuverability sequences based on the angle and the angular direction. ### Claim 8 (depends on 1) The method of claim 1, wherein determining the lateral deviation comprises determining a distance and a shift direction between the first road boundary and the second road boundary, and wherein the first road boundary is parallel to the second road boundary. ### Claim 9 (depends on 8) The method of claim 8, wherein positioning the autonomous vehicle by minimizing the lateral deviation comprises shifting the autonomous vehicle in the plurality of maneuverability sequences based on the distance and the shift direction. ### Claim 10 A system for positioning an autonomous vehicle on a navigation map, the system comprising: a navigation device comprising at least one processor and a computer-readable medium storing instructions that, when executed by the at least one processor, cause the at least one processor to perform operations comprising: receiving the navigation map, an approximate position and an approximate orientation of the autonomous vehicle on the navigation map, and an environmental field of view (FOV) of the autonomous vehicle; determining a first road boundary based on the navigation map and the approximate position of the autonomous vehicle, and a second road boundary based on the environmental FOV and the approximate orientation of the autonomous vehicle; determining at least one of an angular deviation and a lateral deviation between the first road boundary and the second road boundary; positioning the autonomous vehicle on the navigation map by minimizing at least one the angular deviation and the lateral deviation, based on a plurality of maneuverability sequences, wherein the autonomous vehicle is positioned based on command velocities generated for each of the plurality of maneuverability sequences, and wherein a maneuverability sequence from the plurality of maneuverability sequences comprises a trajectory along two arms of a right angle triangle, and wherein a first portion of the trajectory comprises a forward motion along an arm of the triangle opposite to the right angle, and a second portion of the trajectory comprises a reverse motion along an arm adjacent to the right angle of the triangle. ### Claim 11 (depends on 10) The system of claim 10, wherein the navigation map is a pre-generated light detection and ranging (LIDAR) map, wherein the approximate position of the autonomous vehicle is received from a GPS sensor, wherein the approximate orientation of the autonomous vehicle is received from an inertia measurement unit (IMU), and wherein the environmental FOV is received from a LIDAR scanner. ### Claim 12 (depends on 10) The system of claim 10, wherein determining the first road boundary comprises determining a pre-identified road boundary from the navigation map in a direction of movement of the autonomous vehicle, and wherein the direction of movement is determined based on the approximate position of the autonomous vehicle. ### Claim 13 (depends on 10) The system of claim 10, wherein determining the second road boundary comprises determining a road boundary from the environmental FOV with respect to the approximate orientation of the autonomous vehicle by: determining a region in the environmental FOV in a vicinity of at least a portion of the first road boundary; determining a plurality of data points ordered in a straight line within the region and with respect to the approximate orientation of the autonomous vehicle; and determining a road boundary based one the plurality of data points. ### Claim 14 (depends on 10) The system of claim 10, wherein determining the angular deviation comprises determining an angle and an angular direction between the first road boundary and the second road boundary, and wherein positioning the autonomous vehicle by minimizing the angular deviation comprises aligning the autonomous vehicle in parallel to the first road boundary in the plurality of maneuverability sequences based on the angle and the angular direction. ### Claim 15 (depends on 10) The system of claim 10, wherein determining the lateral deviation comprises determining a distance and a shift direction between the first road boundary and the second road boundary, wherein the first road boundary is parallel to the second road boundary, and wherein positioning the autonomous vehicle by minimizing the lateral deviation comprises shifting the autonomous vehicle in the plurality of maneuverability sequences based on the distance and the shift direction. ### Claim 16 A non-transitory computer-readable medium storing computer-executable instructions for: receiving the navigation map, an approximate position and an approximate orientation of the autonomous vehicle on the navigation map, and an environmental field of view (FOV) of the autonomous vehicle; determining a first road boundary based on the navigation map and the approximate position of the autonomous vehicle, and a second road boundary based on the environmental FOV and the approximate orientation of the autonomous vehicle; determining at least one of an angular deviation and a lateral deviation between the first road boundary and the second road boundary; and positioning the autonomous vehicle on the navigation map by minimizing at least one the angular deviation and the lateral deviation, based on a plurality of maneuverability sequences, wherein the autonomous vehicle is positioned based on command velocities generated for each of the plurality of maneuverability sequences, and wherein a maneuverability sequence from the plurality of maneuverability sequences comprises a trajectory along two arms of a right angle triangle, and wherein a first portion of the trajectory comprises a forward motion along an arm of the triangle opposite to the right angle, and a second portion of the trajectory comprises a reverse motion along an arm adjacent to the right angle of the triangle. ### Claim 17 (depends on 16) The non-transitory computer-readable medium of claim 16, wherein determining the first road boundary comprises determining a pre-identified road boundary from the navigation map in a direction of movement of the autonomous vehicle, and wherein the direction of movement is determined based on the approximate position of the autonomous vehicle. ### Claim 18 (depends on 16) The non-transitory computer-readable medium of claim 16, wherein determining the second road boundary comprises determining a road boundary from the environmental FOV with respect to the approximate orientation of the autonomous vehicle by: determining a region in the environmental FOV in a vicinity of at least a portion of the first road boundary; determining a plurality of data points ordered in a straight line within the region and with respect to the approximate orientation of the autonomous vehicle; and determining a road boundary based one the plurality of data points. ### Claim 19 (depends on 16) The non-transitory computer-readable medium of claim 16, wherein determining the angular deviation comprises determining an angle and an angular direction between the first road boundary and the second road boundary, and wherein positioning the autonomous vehicle by minimizing the angular deviation comprises aligning the autonomous vehicle in parallel to the first road boundary in the plurality of maneuverability sequences based on the angle and the angular direction. ### Claim 20 (depends on 16) The non-transitory computer-readable medium of claim 16, wherein determining the lateral deviation comprises determining a distance and a shift direction between the first road boundary and the second road boundary, wherein the first road boundary is parallel to the second road boundary, and wherein positioning the autonomous vehicle by minimizing the lateral deviation comprises shifting the autonomous vehicle in the plurality of maneuverability sequences based on the distance and the shift direction.