# US 2020/0401148 A1 · Path planning for autonomous moving devices > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2020/0401148 A1 - Document ID: US20200401148A1 - Status: Published application - Kind: A1 - Application number: 16/960,706 - Filed: 2018-01-24 - Published: 2020-12-24 - Earliest claimed: 2018-01-24 - Assignees: Ford Global Technologies, LLC - Applicants: Ford Global Technologies, LLC - Inventors: Sanghyun HONG; Jianbo LU; Dimitar FILEV - Web page: https://patentgrep.com/patent/US20200401148A1 ## CPC - G05D 1/0214: {in accordance with safety or protection criteria, e.g. avoiding hazardous areas (monitoring the location of vehicles within a certain area, e.g. forbidden or allowed areas, in traffic control systems for road vehicles G08G1/13)} - B60W 10/00: Conjoint control of vehicle sub-units of different type or different function (for propulsion of purely electrically-propelled vehicles with power supplied within the vehicle B60L50/00 - B60L58/00) - B60W 60/0011: {involving control alternatives for a single driving scenario, e.g. planning several paths to avoid obstacles} - G01C 21/3841: {Data obtained from two or more sources, e.g. probe vehicles} - G01S 13/931: of land vehicles - G01S 17/931: of land vehicles - G05D 1/0088: {characterized by the autonomous decision making process, e.g. artificial intelligence, predefined behaviours (using knowledge based models G06N5/00)} - G05D 1/0223: {involving speed control of the vehicle (vehicle fittings for automatically controlling, i.e. preventing speed from exceeding an arbitrarily established velocity or maintaining speed at a particular velocity, as selected by the vehicle operator B60K31/00)} - G05D 1/0246: {using a video camera in combination with image processing means} - G05D 1/617: Safety or protection, e.g. defining protection zones around obstacles or avoiding hazards (arrangements for controlling the position or course of two or more vehicles for avoiding collisions therebetween G05D1/693; arrangements for reacting to or preventing system or operator failure G05D1/80) - G05D 1/65: Following a desired speed profile - G05D 1/81: Handing over between on-board automatic and on-board manual control - G05D: SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES - B60W: CONJOINT CONTROL OF VEHICLE SUB-UNITS OF DIFFERENT TYPE OR DIFFERENT FUNCTION; CONTROL SYSTEMS SPECIALLY ADAPTED FOR HYBRID VEHICLES; ROAD VEHICLE DRIVE CONTROL SYSTEMS FOR PURPOSES NOT RELATED TO THE CONTROL OF A PARTICULAR SUB-UNIT - 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 ## Abstract The present invention extends to methods, systems, and computer program products for path planning for autonomous moving devices. Aspects of the invention include planning a path for a mobile robot to move autonomously in an environment that includes other static and moving obstacles, such as, for example, other mobile devices and pedestrians, without reference to a prior map of the environment. A planned path for a mobile robot can be determined, adjusted, and adapted using diffusion maps to avoid collisions while making progress towards a global destination. Path planning can include using transition probabilities between grid points to find a feasible path through parts of the environment to make progress towards the global destination. In one aspect, diffusion maps are used in combination with a receding horizon approach, including computing diffusion maps at specified time intervals. ## Claims ### Claim 1 At a mobile device, a method comprising: collecting sensor data from part of an environment between an origin and a destination of the mobile device; creating a diffusion map from the sensor data; determining a path within the part of the environment to make progress towards the destination based on transition probabilities in the diffusion map; and moving the mobile device along the path for a specified amount of time. ### Claim 2 (depends on 1) The method of claim 1, wherein creating a diffusion map from the sensor data comprises generating a local grid map for the part of the environment. ### Claim 3 (depends on 2) The method of claim 2, wherein creating a diffusion map from the sensor data comprises determining the transition probabilities between grid points in the local grid map. ### Claim 4 (depends on 1) The method of claim 1, wherein creating a diffusion map from the sensor data comprises detecting an obstacle within a perception range of one or more sensors attached to the mobile device. ### Claim 5 (depends on 4) The method of claim 4, wherein determining a path within the part of the environment to make progress towards the destination comprises determining a path that avoids the detected obstacle. ### Claim 6 (depends on 5) The method of claim 5, wherein moving the mobile device along the path for a specified amount of time comprises moving the mobile device along the path to avoid the detected obstacle. ### Claim 7 A method for moving a mobile robot from an origin towards a global destination within an environment, the method comprising: receiving a global path to travel from the origin to the global destination within the environment; collecting sensor data from part of the environment; creating a diffusion map for the part of the environment from the sensor data, the diffusion map based on a plurality of grid points and indicating at least one other object within the part of the environment, the diffusion map defining transition probabilities between grid points in the plurality of grid points including taking into account the at least one other object; determining a path to make progress from a current position of the mobile robot in the part of the environment towards the global destination based on the transition probabilities; and moving the mobile robot along the path for a specified amount of time to a local destination. ### Claim 8 (depends on 7) The method of claim 7, further comprising after moving the mobile robot along the path for the specified amount of time: collecting other sensor data from another part of the environment; creating another diffusion map for the other part of the environment from the other sensor data, the other diffusion map including another plurality of grid points, the other diffusion map defining other transition probabilities between grid points in the other plurality of grid points; determining another path to make progress from the local destination towards the global destination based on the other transition probabilities; and moving the mobile robot along the other path for the specified amount of time to another local destination. ### Claim 9 (depends on 7) The method of claim 7, further comprising formulating a local grid map including the plurality of grid points from the sensor data. ### Claim 10 (depends on 7) The method of claim 7, wherein collecting sensor data comprises collecting sensor data from one or more of: a camera, a LIDAR sensor, or a Radar sensor. ### Claim 11 (depends on 7) The method of claim 7, wherein determining a path to make progress from a current position of the mobile robot towards the global destination comprises finding a neighbor grid point with the smallest diffusion distance from current position. ### Claim 12 (depends on 7) The method of claim 7, wherein determining a path to make progress from a current position of the mobile robot towards the global destination comprises determining a path that avoids a collision with the at least one other object. ### Claim 13 (depends on 12) The method of claim 12, wherein determining a path that avoids a collision with the at least one other object comprises determining a path that avoids a collision with moving obstacle. ### Claim 14 (depends on 12) The method of claim 12, wherein moving the mobile robot along the path for a specified amount of time comprises moving the mobile robot around the at least one other object. ### Claim 15 (depends on 7) The method of claim 7, wherein moving the mobile robot along the path for a specified amount of time comprises controlling one or more of: a wheel, a throttle, or a brake at the mobile robot to move the mobile robot along the path. ### Claim 16 A mobile robot, the mobile robot comprising: a processor; and system memory coupled to the processor and storing instructions configured to cause the processor to: collect sensor data from part of an environment; create a diffusion map for the part of the environment from the sensor data, the diffusion map based on a plurality of grid points and indicating at least one other object within the part of the environment, the diffusion map defining transition probabilities between grid points in the plurality of grid points including taking into account the at least one other object; determine a path to make progress from a current position of the mobile robot in the part of the environment towards a global destination based on the transition probabilities; and control motion components of the mobile robot to move the mobile robot along the path for a specified amount of time to a local destination. ### Claim 17 (depends on 16) The mobile robot of claim 16, further comprising instructions configured to cause the processor to: after moving the mobile robot along the path for the specified amount of time: collect other sensor data from another part of the environment; create another diffusion map for the other part of the environment from the other sensor data, the other diffusion map including another plurality of grid points, the other diffusion map defining other transition probabilities between grid points in the other plurality of grid points; determine another path to make progress from the local destination towards the global destination based on the other transition probabilities; and control the motion components to move the mobile robot along the other path for the specified amount of time to another local destination. ### Claim 18 (depends on 16) The mobile robot of claim 16, further comprising instructions configured to cause the processor to formulate a local grid map including the plurality of grid points from the sensor data. ### Claim 19 (depends on 16) The mobile robot of claim 16, wherein instructions configured to cause the processor to determine a path to make progress from a current position of the mobile robot towards the global destination comprise instructions configured to cause the processor to find a neighbor grid point with the smallest diffusion distance from current position. ### Claim 20 (depends on 16) The mobile robot of claim 16, wherein instructions configured to cause the processor to control motion components of the mobile robot to move the mobile robot along the path comprise instructions configured to cause the processor to control the motion components to avoid colliding with the at least one other object.