# US 12,602,052 B2 · Method and apparatus with navigation path generation > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,602,052 B2 - Document ID: US12602052B2 - Status: Granted - Kind: B2 - Application number: 18/603,687 - Filed: 2024-03-13 - Published: 2024-09-19 - Granted: 2026-04-14 - Earliest claimed: 2023-03-13 - Assignees: Electronics and Telecommunications Research Institute - Applicants: Electronics and Telecommunications Research Institute - Inventors: Seohyun Jeon; SeungHwan Park; Jae-Yeong Lee; Seung-lk Lee; Jae Ho Lim; Seung Min Choi - Web page: https://patentgrep.com/patent/US12602052B2 ## CPC - G05D 1/229: Command input data, e.g. waypoints - G01C 21/3407: {specially adapted for specific applications} - G01C 21/3807: {characterised by the type of data} - G05D 1/242: Means based on the reflection of waves generated by the vehicle (using passive navigation aids external to the vehicle G05D1/244; using signals provided by artificial sources external to the vehicle G05D1/247) - G05D 1/2464: {using an occupancy grid} - G05D 1/2469: {using a topologic or simplified map} - G05D 1/644: Optimisation of travel parameters, e.g. of energy consumption, journey time or distance - G05D 2107/17: Spaces with priority for humans, e.g. populated areas, pedestrian ways, parks or beaches - G05D: SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES - 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) ## Abstract A method and apparatus of generating a path for autonomous navigation of a mobile computing apparatus is provided. The mobile computing apparatus includes one or more processors configured to map a set global path, which connects a current position of the mobile computing apparatus with a future destination of the mobile computing apparatus based on a topology map, to a real-time generated occupancy grid map that represents, based on sensor data of a surrounding environment of the mobile computing apparatus, an un-drivable area and a drivable area in the surrounding environment, and generate a local path, for a traveling of the mobile computing apparatus, connecting the current position with a sub-waypoint that corresponds to the drivable area in response to a next waypoint, to which the mobile computing apparatus is set to travel based on the global path, being determined to correspond to the un-drivable area. ## Claims ### Claim 1 A processor-implemented method of a mobile computing apparatus, the method comprising: generating a global path connecting a current position of the mobile computing apparatus with a future destination of the mobile computing apparatus based on a topology map that is generated based on mapping information; generating, in real time, an occupancy grid map based on sensor data obtained from a sensor of the mobile computing apparatus, the occupancy grid map representing an un-drivable area and a drivable area in a surrounding environment of the mobile computing apparatus; mapping the global path to the occupancy grid map; generating a sub-waypoint located in the drivable area in response to a next waypoint, to which the mobile computing apparatus is set to travel based on the global path, being determined to correspond to the un-drivable area, where the next waypoint is among a plurality of waypoints included in the global path; and generating a local path, for a traveling of the mobile computing apparatus, connecting the current position with the sub-waypoint. ### Claim 2 (depends on 1) The method of claim 1, further comprising: downloading the mapping information from a device that is external of the mobile computing apparatus; determining nodes corresponding to the plurality of waypoints and edges connecting the nodes with one another from the mapping information; and generating the topology map based on the nodes and the edges. ### Claim 3 (depends on 1) The method of claim 1, wherein the generating of the global path comprises: selecting nodes, from among a plurality of nodes of the topology map, connecting the current position of the mobile computing apparatus with the destination of the mobile computing apparatus; setting the selected nodes to be the plurality of waypoints; and generating the global path including the plurality of waypoints and edges connecting the plurality of waypoints. ### Claim 4 (depends on 1) The method of claim 1, wherein the mapping of the global path to the occupancy grid map comprises converting coordinate values of a plurality of nodes of the global path into coordinate values in a coordinate system of the mobile computing apparatus. ### Claim 5 (depends on 1) The method of claim 1, wherein the generating of the sub-waypoint comprises: generating a straight line connecting a current waypoint, representing the current position of the mobile computing apparatus, with the next waypoint in the occupancy grid map; and determining, as the sub-waypoint, a candidate waypoint determined to be located farthest away from the current waypoint in the drivable area from among a plurality of candidate waypoints along the straight line. ### Claim 6 (depends on 1) The method of claim 1, wherein the generating of the sub-waypoint comprises: generating a straight line connecting a current waypoint, representing the current position of the mobile computing apparatus, with the next waypoint in the occupancy grid map; selecting, from among a plurality of first candidate waypoints located along the straight line, a first candidate waypoint determined to be located farthest away from the current waypoint in the drivable area; and in response to a determined distance between the current waypoint and the first candidate waypoint being determined to be less than a reference distance: rotating the straight line with respect to the current waypoint; selecting, from among a plurality of second candidate waypoints located along the rotated straight line, a second candidate waypoint determined to be located farthest away from the current waypoint in the drivable area; and in response to a distance value between the current waypoint and the second candidate waypoint being determined to be greater than or equal to the reference distance value, determine the second candidate waypoint to be the sub-waypoint. ### Claim 7 A mobile computing apparatus, comprising: one or more processors configured to: map a set global path, which connects a current position of the mobile computing apparatus with a future destination of the mobile computing apparatus based on a topology map, to a real-time generated occupancy grid map that represents, based on sensor data of a surrounding environment of the mobile computing apparatus, an un-drivable area and a drivable area in the surrounding environment; and generate a local path, for a traveling of the mobile computing apparatus, connecting the current position with a sub-waypoint that corresponds to the drivable area in response to a next waypoint, to which the mobile computing apparatus is set to travel based on the global path, being determined to correspond to the un-drivable area. ### Claim 8 (depends on 7) The apparatus of claim 7, wherein the topology map is based on mapping information generated external of the mobile computing apparatus, and wherein the one or more processors are further configured to generate in real-time, with respect to the mobile computing apparatus being at the current position, the occupancy grid map representing the un-drivable area and the drivable area based on the sensor data that is obtained from a sensor of the mobile computing apparatus. ### Claim 9 (depends on 7) The apparatus of claim 7, wherein the one or more processors are configured to generate the global path, including the one or more processors being configured to: select, from among a plurality of nodes in the topology map, nodes connecting the current position with the future destination as waypoints of the mobile computing apparatus; and generate the global path including the waypoints and edges of the topology map that connect the waypoints with one another. ### Claim 10 (depends on 9) The apparatus of claim 9, wherein the mobile computing apparatus is a mobile robot that further comprises a driving motor, and wherein the one or more processors are further configured to cause the traveling of the mobile computing apparatus according to the generated local path. ### Claim 11 (depends on 10) The apparatus of claim 10, wherein the one or more processors are further configured to generate the topology map based on mapping information generated external of the mobile computing apparatus. ### Claim 12 (depends on 7) The apparatus of claim 7, further comprising a communication device, wherein the one or more processors are further configured to: download mapping information, from a device that is external of the mobile computing apparatus, using the communication device; determine nodes corresponding to a plurality of waypoints and edges connecting the nodes with one another from the mapping information; and generate the topology map based on the nodes and edges. ### Claim 13 (depends on 7) The apparatus of claim 7, wherein the one or more processors are configured to generate the sub-waypoint located in the drivable area, including the one or more processors being configured to: determine, in the occupancy grid map, a straight line connecting a current waypoint, representing the current position of the mobile computing apparatus, with the next waypoint; and project the next waypoint into the drivable area based on the straight line. ### Claim 14 (depends on 13) The apparatus of claim 13, wherein, for the projection of the next waypoint, the one or more processors are configured to select the sub-waypoint, from among a plurality of candidate waypoints in the drivable area that are determined based on the straight line, that is determined to be located farthest away from the current waypoint among the plurality of candidate waypoints. ### Claim 15 (depends on 13) The apparatus of claim 13, wherein, for the projection of the next waypoint, the one or more processors are configured to: determine a first candidate waypoint that is located in the drivable area farthest away, along the straight line, from the current waypoint; and in response to a determined distance between the current waypoint and the first candidate waypoint being determined to be less than a reference distance: rotate the straight line; select, from among a plurality of second candidate waypoints in the drivable area that are determined based on the rotated straight line, a second candidate waypoint determined to be located farthest away from the current waypoint in the drivable area; and determine the sub-waypoint dependent on the second candidate waypoint. ### Claim 16 (depends on 15) The apparatus of claim 15, wherein, for the determining of the sub-waypoint dependent on the second candidate waypoint, the one or more processors are configured to, in response to a determined distance value between the current waypoint and the second candidate waypoint being greater than or equal to the reference distance value, determine the sub-waypoint to be the second candidate waypoint. ### Claim 17 A processor-implemented method of a mobile computing apparatus, the method comprising: mapping a set global path, which connects a current position of the mobile computing apparatus with a future destination of the mobile computing apparatus based on a topology map, to a real-time generated occupancy grid map that represents, based on sensor data of a surrounding environment of the mobile computing apparatus, an un-drivable area and a drivable area in the surrounding environment; and generating a local path, for a traveling of the mobile computing apparatus, connecting the current position with a sub-waypoint that corresponds to the drivable area in response to a next waypoint, to which the mobile computing apparatus is set to travel based on the global path, being determined to correspond to the un-drivable area, wherein the topology map is based on mapping information generated external of the mobile computing apparatus. ### Claim 18 (depends on 17) The method of claim 17, further comprising generating in real-time, with respect to the mobile computing apparatus being at the current position, the occupancy grid map representing the un-drivable area and the drivable area based on the sensor data that is obtained from a sensor of the mobile computing apparatus. ### Claim 19 (depends on 17) The method of claim 17, further comprising: downloading the mapping information from a device external of the mobile computing apparatus; determining nodes corresponding to a plurality of waypoints and edges connecting the nodes with one another from the mapping information; generating the topology map based on the nodes and edges. ### Claim 20 (depends on 17) The method of claim 17, further comprising generating the sub-waypoint located in the drivable area, comprising: determining, in the occupancy grid map, a straight line connecting a current waypoint, representing the current position of the mobile computing apparatus, with the next waypoint; selecting a first candidate waypoint determined to be located farthest away from the current waypoint in the drivable area from among a plurality of candidate waypoints determined along the straight line; and in response to a determined distance between the current waypoint and the first candidate waypoint being less than a reference distance: rotating the straight line with respect to the current waypoint; selecting a second candidate waypoint determined to be located farthest away from the current waypoint in the drivable area from among a plurality of candidate waypoints determined along the rotated straight line; and in response to a determined distance between the current waypoint and the second candidate waypoint being greater than or equal to the reference distance value, determining the sub-waypoint to be the second candidate waypoint.