Search

DE-112018006578-B4 - WAY PLANNING FOR AUTONOMOUS MOVING DEVICES

DE112018006578B4DE 112018006578 B4DE112018006578 B4DE 112018006578B4DE-112018006578-B4

Abstract

Procedure, comprehensive: Collecting sensor data (208) from a part of an environment (200) between a point of origin (261) and a point of destination of a mobile device; Creating a diffusion map (209, 406) from the sensor data (208), wherein the diffusion map (209, 406) is based on a plurality of grid points and shows an object (221A, 221B, 221C) in the part of the environment (200), wherein the diffusion map (209, 406) defines transition probabilities (263) between grid points of the plurality of grid points; Determining a path (217) within the part of the environment (200) to approach the destination based on transition probabilities (263) in the diffusion map (209, 406) and applying a retreating horizon control each time the mobile device has moved towards the target (404) at a specified speed for a specified time period, wherein the retreating horizon control uses predictions of future costs, disturbances and/or constraints over a sliding time horizon to select a control action; Assigning an estimated radius, which is smaller than a detection range (523) of one or more sensors (202, 402) attached to the mobile device, to the object (221A, 221B, 221C); Avoiding a collision with the object (221A, 221B, 221C) based on the estimated radius; and Moving the mobile device along the path (217) to a local destination.

Inventors

  • Sanghyun Hong
  • Jianbo Lu
  • Dimitar Filev

Assignees

  • FORD GLOBAL TECHNOLOGIES, LLC

Dates

Publication Date
20260513
Application Date
20180124

Claims (16)

  1. Method comprising: Collecting sensor data (208) from a portion of an environment (200) between a source (261) and destination location of a mobile device; Creating a diffusion map (209, 406) from the sensor data (208), wherein the diffusion map (209, 406) is based on a plurality of grid points and shows an object (221A, 221B, 221C) in the portion of the environment (200), and wherein the diffusion map (209, 406) defines transition probabilities (263) between grid points of the plurality of grid points; Determining a path (217) within the part of the environment (200) to approach the destination based on transition probabilities (263) in the diffusion map (209, 406) and applying a retreating horizon control each time the mobile device has moved towards the target (404) at a specified speed for a specified time period, the retreating horizon control using predictions of future costs, disturbances, and/or constraints over a sliding time horizon to select a control action; Assigning an estimated radius, smaller than a detection range (523) from one or more sensors (202, 402) attached to the mobile device, to the object (221A, 221B, 221C); Avoiding a collision with the object (221A, 221B, 221C) based on the estimated radius; and moving the mobile device along the path (217) to a local destination.
  2. Procedure according to Claim 1 , wherein creating a diffusion map (209, 406) from the sensor data (208) includes generating a local raster map (226) for the part of the environment (200), wherein applying the retreating horizon control includes predicting future costs, disturbances and/or constraints over a moving time horizon to select a control action.
  3. Procedure according to Claim 1 , wherein creating a diffusion map (209, 406) from the sensor data (208) comprises: detecting an obstacle (221A, 221B, 221C, 524) within a detection range (523) of one or more sensors (202, 402) attached to the mobile device; assigning an estimated radius, which is smaller than a detection range (523) of one or more sensors (202, 402) attached to the mobile device, to the obstacle (221A, 221B, 221C, 524); and determining an adjacent grid point by using the estimated radius.
  4. Procedure according to Claim 3 , wherein moving the mobile device along the path (217) includes avoiding the obstacle (221A, 221B, 221C, 524).
  5. A method for moving a mobile robot (201) from an origin (261) to a global destination (262) within an environment (200), the method comprising: collecting sensor data (208) from a part of the environment (200); creating a diffusion map (209) for the part of the environment (200) from the sensor data (208), wherein the diffusion map (209) is based on a plurality of grid points, and specifying an object (221A, 221B, 221C) within the part of the environment (200), wherein the diffusion map (209) defines transition probabilities (263) between grid points in the plurality of grid points; Determining a path (217) to approach the global destination (262) from the current position of the mobile robot (201) in the part of the environment (200), based on the transition probabilities (263) in the diffusion map (209) and applying a retreating horizon control each time the mobile robot (201) has moved toward the global destination at a specified speed for a specified time period, the retreating horizon control using predictions of future costs, disturbances, and/or constraints over a sliding time horizon to select a control action; Assigning an estimated radius, smaller than a detection range (263) from one or more sensors (202) attached to the mobile robot (201), to the object (221A, 221B, 221C); Avoiding a collision with the object (221A, 221B, 221C) based on the estimated radius; and Moving the mobile robot (201) along the path (217) to a local destination.
  6. Procedure according to Claim 5 , furthermore comprehensively after moving the mobile robot (201) along the path (217) to the local destination: Collecting other sensor data (208) from another part of the environment (200); creating another diffusion map (209) for the other part of the environment (200) from the other sensor data (208), wherein the other diffusion map (209) includes a different set of grid points, wherein the other diffusion map (209) defines other transition probabilities (263) between grid points in the other set of grid points; determining another path (217) to approach the global destination (262) from the local destination based on the other transition probabilities (263); and moving the mobile robot (221) along the other path (217) to another local destination.
  7. Procedure according to Claim 5 , wherein determining a path (217) to approach the global destination (262) from a current position of the mobile robot (201) includes finding a neighboring grid point with the smallest diffusion distance from the current position.
  8. Procedure according to Claim 5 , wherein determining a path (217) to approach the global destination (262) from a current position of the mobile robot (201) includes determining a path (217) that avoids a collision with the at least one other object (221A, 221B, 221C).
  9. Procedure according to Claim 8 , wherein determining a path (217) that avoids a collision with the at least one other object (221A, 221B, 221C) includes determining a path (217) that avoids a collision with a moving obstacle (221A, 221B, 221C).
  10. Procedure according to Claim 8 , wherein moving the mobile robot (201) along the path (217) includes moving the mobile robot (201) around the at least one other object (221A, 221B, 221C).
  11. Procedure according to Claim 5 , wherein moving the mobile robot (201) along the path (217) for a specified period of time includes controlling one or more of the following: a wheel (241), a throttle (242) or a brake (243) on the mobile robot (201) to move the mobile robot (201) along the path (217).
  12. Mobile robot (201), wherein the mobile robot (201) comprises: a processor (102); and a system memory coupled to the processor (102) and storing instructions configured to cause the processor (102) to: collect sensor data (208) from a part of an environment (200); create a diffusion map (209) for the part of the environment (200) from the sensor data (208), wherein the diffusion map (209) is based on a plurality of grid points; and specify an object (221A, 221B, 221C) within the part of the environment (200), wherein the diffusion map (209) defines transition probabilities (263) between grid points in the plurality of grid points; Determining a path (217) to approach a global destination (262) from the current position of the mobile robot (201) in the part of the environment (200), based on transition probabilities (263) in the diffusion map (209) and applying a retreating horizon control each time the mobile robot (201) has moved toward the global destination at a specified speed for a specified time period, the retreating horizon control using predictions of future costs, disturbances, and/or constraints over a sliding time horizon to select a control action; Assigning an estimated radius, smaller than a detection range (263) from one or more sensors (202) attached to the mobile robot (201), to the object; Avoiding a collision with the object (221A, 221B, 221C) based on the estimated radius; and controlling motion components (254) of the mobile robot (201) to move the mobile robot (201) along the path (217) to a local destination.
  13. Mobile robot (201) according to Claim 12 , furthermore comprising instructions configured to cause the processor (102) to: move the mobile robot (201) along the path (217); collect other sensor data (208) from another part of the environment (200); create another diffusion map (209) for the other part of the environment (200) from the other sensor data (208), wherein the other diffusion map (209) includes a different set of grid points, and wherein the other diffusion map (209) defines different transition probabilities (263) between grid points in the other set of grid points; determine another path (217) to approach the global destination (262) from the local destination based on the other transition probabilities (263); and control the motion components to to move the mobile robot (201) along the other path (217) to another local destination for the specified duration.
  14. Mobile robot (201) according to Claim 12 , furthermore, comprehensive instructions configured to cause the processor (102) to formulate a local raster map containing the multitude of raster points from the sensor data (208).
  15. Mobile robot (201) according to Claim 12 , wherein instructions configured to cause the processor (102) to determine a path (217) to approach the global destination (262) from a current position of the mobile robot (201) include instructions configured to cause the processor (102) to find an adjacent grid point with the smallest diffusion distance from the current position.
  16. Mobile robot (201) according to Claim 12 , wherein instructions configured to cause the processor (102) to control motion components (254) of the mobile robot (201) to move the mobile robot (201) along the path (217) include instructions configured to cause the processor (102) to control the motion components (254) to avoid a collision with the object (221A, 221B, 221C).

Description

CROSS-REFERENCE TO RELATED REGISTRATIONS Not applicable. GENERAL STATE OF THE ART 1. Field of the invention This invention relates generally to the field of automated devices and in particular to path planning for autonomous moving devices. 2. Relevant state of the art Mobile robots have been developed for a wide range of applications, including transportation, search and rescue, and surveillance. To help ensure safe operation, mobile robots can adapt their routes to changing environments, such as streets with newly constructed buildings, other moving obstacles, and so on. Mobile robots can store a map of an operational area and navigate along predefined routes or modify routes as needed. State of the art includes... DE 102013 219 414 A1 and DE 10 2013 225 057 A1 to be taken. BRIEF DESCRIPTION OF THE DRAWINGS The specific features, aspects and advantages of the present invention will be better understood with reference to the following description and the accompanying drawings, in which the following applies: 1 This illustrates an example block diagram of a computing device. 2 illustrates an exemplary computer architecture that enables the planning of a path for a mobile robot. 3 illustrates a flowchart of an exemplary procedure for planning a path for a mobile robot. 4 illustrates an exemplary data flow for collision avoidance based on diffusion maps. 5 illustrates an example of an enlarged section of a raster map that includes a target point. The 6A-6J Illustrate exemplary equations for calculating diffusion maps. 7 illustrates an example algorithm for finding a local path from a starting point to a local destination point. The 8A-8C illustrates an example of moving a mobile robot from a point of origin to a global destination across the raster map. 5 . DETAILED DESCRIPTION The present invention relates to methods, systems, and computer program products for path planning for autonomous moving devices. Mobile devices, and in particular mobile robots, have been considered for various applications, including logistics robots, home robots, automated guided vehicles, and delivery robots. Depending on the type and configuration of a mobile robot, it can transport goods or freight as an alternative to manual transport by human carriers. Mobile robots can navigate along predefined routes or change a route at will. Using a previous map of an operational area, path planning for mobile robots can be based on a variety of different algorithms. Path planning algorithms can find routes with minimum cost within a fixed graph. To account for changes in the environment, existing paths can be incrementally repaired based on previous paths. Some path planning algorithms quickly identify a suboptimal path and then refine it into a more optimal one. Path planning algorithms can also use guidelines generated through reinforcement learning to avoid collisions based on a planned path using diffusion maps. Aspects of the invention include planning a path for a mobile robot to move autonomously in an environment containing other moving objects, such as other mobile devices and pedestrians, without reference to a prior map of the environment. A planned path for a mobile robot can be determined, set, and adjusted to avoid collisions in a dynamic environment while approaching a destination. A mobile robot can navigate from a point of origin to a destination within an environment using diffusion maps. Sensors attached to the mobile robot can Collect sensor data from an area around the mobile robot (i.e., a portion of its environment). A raster map of this area can be formulated from the collected sensor data. The raster map can contain a multitude of raster points. An underlying geometry (manifold) of the raster map can be determined for the area. Path planning can involve using transition probabilities between grid points to find a feasible route through the area to approach the destination. One aspect uses diffusion maps in combination with a retreating horizon approach, which involves calculating a diffusion map at fixed intervals. Using diffusion maps with a retreating horizon approach essentially eliminates the need to store a previous map. 1 Figure 1 illustrates an example block diagram of a computing device 100. The computing device 100 can be used to perform various operations, such as those discussed in this document. The computing device 100 can function as a server, a client, or any other computing unit. The computing device 100 can perform various communication and data transmission functions, as described in this document, and can execute one or more application programs, such as those described in this document. The computing device 100 can be any of a wide variety of computing devices, such as a mobile phone or other mobile device, a desktop computer, a notebook computer, a server computer, a handheld computer, a tablet computer, and the like. The computing device 100 includes one or more processors 102, one or more mem