System and method for localization of robots

• US 9,927,814 B2
• Filed: 03/28/2016
• Issued: 03/27/2018
• Est. Priority Date: 03/28/2016
• Status: Active Grant

• Current Assignee: Zebra Technologies Corporation
• Original Assignee: Fetch Robotics, Inc. (Zebra Technologies Corporation)
• Inventors: Wise, Melonee, Ferguson, Michael
• Primary Examiner(s): ARTHUR JEANGLAUDE, GERTRUDE
• Application Number:
  US15/082,488
• Publication Number:
  US 20170276501A1
• Time in Patent Office: 729 Days
• Field of Search: 701 26, 701522, 701532, 701 2, 701461, 901 7, 700245, 700258, 700259
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: G05D 1/0248 in combination with a laser lasers per se H01S
• CPC Class Codes: G05D 1/0272 comprising means for registering the travel distance, e.g. revolutions of wheels measuring distance traversed on the ground by vehicles, e.g. using odometers G01C22/00
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30

Abstract

A method for localization of robots in a territory of interest includes: providing a mobile robot comprising a processor configured to compute an estimated pose of the mobile robot in a map of a territory of interest using a particle filter comprising a particle; updating, by the processor, a pose in the map of the particle; deciding, by the processor, whether to retain the particle for the next cycle of the particle filter or to eliminate the particle for the next cycle of the particle filter; and sampling the particle filter, by the processor, so as to achieve localization of robots in a territory of interest.

Claims

1. A method for localization of robots in a territory of interest, comprising:

updating, by a processor configured to compute an estimated pose of a mobile robot in a map of a territory of interest using a particle filter comprising a particle, a pose in the map of the particle, the particle filter comprising all particles retained from a previous cycle;

deciding, by the processor, whether to retain the particle for a next cycle of the particle filter or to eliminate the particle for the next cycle of the particle filter, wherein deciding further comprises applying a decision criterion comprising an obstacle analysis;

and sampling the particle filter, by the processor, so as to achieve localization of robots in a territory of interest, wherein the map comprises a heat map of one or more networks sensed by the robots.

2. The method of claim 1, wherein updating comprises building the map using techniques in Simultaneous Mapping and Localization (SLAM).

3. The method of claim 1, wherein the map comprises a heat map of one or more sensed networks.

10. The method of claim 1, wherein the step of updating is performed at runtime.

11. The method of claim 1, wherein the step of updating further comprises using sensed data.

12. The method of claim 1, wherein the step of updating further comprises adding a new network to the map based on a current best estimate of robot pose.

13. The method of claim 1, wherein the step of updating further comprises pooling map updates, by two or more robots.

14. The method of claim 13, wherein the step of updating further comprises storing, by at least one of the two or more robots, a second map comprising differences sensed from the original map.

15. The method of claim 14, wherein the step of updating further comprises collecting the difference maps.

16. The method of claim 15, where the step of updating comprises determining which updates have strong correlation between the one or more robots.

17. The method of claim 1, wherein the step of updating is performed based on an odometry measurement of the robot.

18. The method of claim 1, wherein the step of updating is performed using one or more of a scanning laser range finder and depth camera to clear out a mapped obstacles that is no longer present in the real world.

19. The method of claim 1, wherein the step of updating further comprises predicting Gaussian noise.

20. The method of claim 1, wherein the step of updating further comprises leaving a particle in place based on the odometry measurement of the robot.

21. The method of claim 1, wherein the step of updating further comprises associating a particle in a particle filter with the particle pose.

23. The method of claim 1, wherein the step of deciding further comprises removing particles where a wireless network should not be seen.

24. The method of claim 1, wherein the particle pose comprises information regarding one or more of a pose of the robot in three-dimensional space and an orientation of the robot in three-dimensional space.

25. The method of claim 24, wherein the particle pose further comprises a quaternion describing one or more of the robot'"'"'s roll, pitch, and yaw.

26. The method of claim 1, wherein the territory of interest comprises an obstacle.

27. The method of claim 26, wherein the obstacle comprises a wall.

28. The method of claim 1, wherein the map comprises network data.

29. The method of claim 1, wherein deciding further comprises applying two decision criteria.

30. The method of claim 29, wherein one of the decision criteria comprises an obstacle analysis.

31. The method of claim 30, wherein the obstacle analysis comprises comparing the particle to the map, so as to determine whether the particle has passed through one or more of a wall and another obstacle.

32. The method of claim 31, wherein if the particle has passed through the one or more of a wall and another obstacle, deciding comprises eliminating the particle.

33. The method of claim 31, wherein if the particle has not passed through the one or more of a wall and another obstacle, deciding comprises retaining the particle.

34. The method of claim 30, wherein the obstacle analysis comprises computation of whether a point is in contact with an obstacle.

35. The method of claim 34, wherein the computation of whether a point is in contact with an obstacle becomes a determination whether a point representing the center of the robot lies inside a bounding volume, the bounding volume comprising a radius of the obstacle inflated by the radius of the mobile robot base.

36. The method of claim 30, wherein the obstacle analysis comprises inflating a size of one or more obstacles.

37. The method of claim 36, wherein the obstacle analysis comprises inflating the size of the one or more obstacles by an approximate radius of a base of the mobile robot.

38. The method of claim 29, wherein one of the decision criteria comprises a network analysis.

39. The method of claim 38, wherein the network analysis comprises comparing existing networks to networks observed by the robot.

40. The method of claim 39, wherein if a network that is sensed by the robot does not exist at the pose of the particle, deciding comprises eliminating the particle.

41. The method of claim 39, wherein if the network that is sensed by the robot does exist at the pose of the particle, deciding comprises retaining the particle.

42. The method of claim 29, wherein one of the decision criteria comprises a known object analysis.

43. The method of claim 42, wherein the known object analysis comprises comparing existing known objects to known objects observed by the robot.

44. The method of claim 43, wherein if a known object is sensed by a robot that does not exist at the pose of the particle, deciding comprises eliminating the particle.

45. The method of claim 43, wherein if a known object is sensed by a robot that does exist at the pose of the particle, deciding comprises retaining the particle.

46. The method of claim 1, wherein sampling comprises sampling the particles so as to maintain enough particles for the particle filter to function.

47. The method of claim 46, wherein sampling further comprises sampling the particles so as to maintain enough particles for the particle filter to function at a predetermined level of effectiveness.

48. The method of claim 1, wherein sampling comprises sampling new particles to be added to the retained particles.

49. The method of claim 1, wherein sampling comprises sampling new particles selected from a distribution having desired characteristics.

50. The method of claim 49, wherein sampling comprises sampling new particles selected from a substantially Gaussian distribution having desired characteristics.

51. The method of claim 1, wherein sampling comprises sampling new particles having a mean related in a desired way to the mean of the retained particles.

52. The method of claim 51, wherein sampling comprises sampling new particles having a mean approximately equal to a mean of the retained particles.

53. The method of claim 1, wherein sampling comprises sampling new particles having a covariance related in a desired way to the covariance of the retained particles.

54. The method of claim 53, wherein sampling further comprises sampling new particles having a covariance approximately equal to a covariance of the retained particles.

55. The method of claim 1, wherein the sampling step comprises a sub-step of weighting two or more particles.

56. The method of claim 55, wherein the sub-step of weighting comprises evaluating a particle without a feature if the feature causes a large majority of the present particles of the filter to be reduced in weight.

57. The method of claim 56, wherein the feature comprises one or more of a sensed object and a sensed network.

58. The method of claim 55, wherein the sub-step of weighting comprises weighting two or more particles using weights that are all substantially equal.

59. The method of claim 55, wherein the sub-step of weighting comprises weighting two or more particles using weights that are not all substantially equal.

60. The method of claim 55, wherein the sub-step of weighting comprises deriving at least one of the weights using a correlation between sensed network strength and predicted network strength.

61. The method of claim 55, wherein the sub-step of weighting comprises deriving at least one of the weights using one or more of a sensed presence of one or more known objects and a sensed absence of one or more known objects.

62. The method of claim 55, wherein the sub-step of weighting comprises deriving at least one of the weights using one or more of a sensed presence of one or more environmental signs and a sensed absence of one or more environmental signs.

63. The method of claim 62, wherein the sub-step of weighting further comprises deriving at least one of the weights using one or more of a sensed presence in a predicted map area of an environmental sign and a sensed absence in a predicted map area of an environmental sign.

64. The method of claim 63, wherein the environmental sign comprises one or more of a fiducial, an aisle number, a row number, a magnetic field, an electric field, and another environmental sign.

65. The method of claim 55, wherein the sub-step of weighting comprises using respective weights of at least two particles to help determine which particles should be eliminated from the particle filter.

66. The method of claim 1, wherein at least one of updating, deciding, and sampling is performed by a microprocessor comprised in an actuator instead of by the processor.

4. A method for localization of robots in a territory of interest, comprising:

updating, by a processor configured to compute an estimated pose of a mobile robot in a map of a territory of interest using a particle filter comprising a particle, a pose in the map of the particle, the particle filter comprising all particles retained from a previous cycle;

deciding, by the processor, whether to retain the particle for a next cycle of the particle filter or to eliminate the particle for the next cycle of the particle filter, wherein deciding further comprises applying a decision criterion comprising an obstacle analysis;

and sampling the particle filter, by the processor, so as to achieve localization of robots in a territory of interest, wherein the map comprises a location of one or more known objects.

5. The method of claim 4, wherein the known object comprises one or more of a charging dock, a piece of office furniture, a robotic workcell, and another known object.

6. The method of claim 4, wherein the map comprises a location of one or more known objects.

7. The method of claim 6, wherein the location of the one or more known objects is included in the map by allowing a robotic perception module to detect the one or more known objects during the building of the map.

8. The method of claim 6, wherein the location of the one or more known objects is included in the map by allowing the robotic perception module to add the location after map building using stored data.

9. The method of claim 6, wherein the location of the one or more known objects is included in the map by allowing human annotators to manually add the location using an interface.

22. A method for localization of robots in a territory of interest, comprising:

updating, by a processor configured to compute an estimated pose of a mobile robot in a map of a territory of interest using a particle filter comprising a particle, a pose in the map of the particle, the particle filter comprising all particles retained from a previous cycle;

deciding, by the processor, whether to retain the particle for a next cycle of the particle filter or to eliminate the particle for the next cycle of the particle filter, wherein deciding further comprises applying a decision criterion comprising an obstacle analysis; and

sampling the particle filter, by the processor, so as to achieve localization of robots in a territory of interest, wherein the step of deciding further comprises removing particles that pass through obstacles.

67. A method for localization of robots in a territory of interest, comprising:

building, by a processor configured to compute an estimated pose of a mobile robot in a territory of interest using a particle filter comprising a particle, a map of the territory of interest, the particle filter comprising all particles retained from a previous cycle;

updating, by the processor, a pose of the particle in the map;

associating, by the processor, the particle with the particle pose;

deciding, by the processor, whether to retain the particle for a next cycle of the particle filter or to eliminate the particle for the next cycle of the particle filter, wherein deciding further comprises applying a decision criterion comprising data from a network sensor configured to sense one or more of presence and strength of a network;

sampling the particle filter, by the processor; and

determining, by the processor, that further associating of the particle with the particle pose is not required to maintain enough particles for the particle filter to function, so as to achieve localization of robots in a territory of interest.

68. The method of claim 67, wherein the sampling step comprises weighting two or more particles.

69. The method of claim 68, wherein weighting comprises deriving at least one of the weights using a correlation between sensed network strength and predicted network strength.

70. The method of claim 68, wherein weighting comprises deriving at least one of the weights using one or more of a sensed presence of one or more known objects and a sensed absence of one or more known objects.

71. The method of claim 68, wherein weighting comprises deriving at least one of the weights using one or more of a sensed presence of one or more environmental signs and a sensed absence of one or more environmental signs.

72. The method of claim 71, wherein weighting further comprises deriving at least one of the weights using one or more of a sensed presence in a predicted map area of an environmental sign and a sensed absence in a predicted map area of an environmental sign.

73. The method of claim 72, wherein the environmental sign comprises one or more of a fiducial, an aisle number, a row number, a magnetic field, an electric field, and another environmental sign.

74. The method of claim 68, wherein weighting comprises using respective weights of at least two particles to help determine which particles should be eliminated from the particle filter.

75. A system for localization of robots in a territory of interest, comprising:

a mobile robot comprising a processor, the mobile robot further comprising an actuator; and

a sensor configured to measure the movement of the mobile robot, wherein the actuator comprises a microprocessor equipped with a program configured to execute steps in a particle-based method for robot localization, the steps comprising;

updating, by the processor, a pose in a map of the particle, the particle filter comprising all particles retained from a previous cycle;

deciding, by the processor, whether to retain the particle for a next cycle of a particle filter or to eliminate the particle for the next cycle of the particle filter, wherein deciding further comprises applying a decision criterion comprising data from a network sensor configured to sense one or more of presence and strength of a network; and

sampling the particle filter, by the processor, so as to achieve localization of robots in a territory of interest.

76. The system of claim 75, wherein the mobile robot comprises the sensor.

77. The system of claim 75, wherein the sensor comprises a device configured to measure the movement of the mobile robot using odometry.

78. The system of claim 75, wherein the mobile robot comprises one or more wheels.

79. The system of claim 78, wherein the sensor is configured to measure movement of one or more of the one or more the wheels.

80. The system of claim 75, wherein the robot comprises an actuator motor configured to move the actuator.

81. The system of claim 80, wherein the actuator motor is mechanically attached to the actuator.

82. The system of claim 80, wherein the actuator motor is remotely activated using one or more of a belt and a non-belt power transmission device.

83. The system of claim 75, wherein the actuator comprises a feedback mechanism configured to provide feedback to the actuator.

84. The system of claim 83, wherein the actuator feedback comprises one or more of information regarding a position of the actuator, information regarding a force on the actuator, information regarding a position of the actuator, information regarding the operation of the actuator, and other actuator feedback.

85. The system of claim 83, wherein the feedback mechanism comprises one or more of a torque sensor and a tactile sensor.

86. The system of claim 75, wherein the actuator comprises one or more of an appendage, an appendage joint, and a wheel.

87. The system of claim 86, wherein the appendage comprises one or more of an arm, a leg, and another appendage.

88. The system of claim 75, wherein the actuator comprises a microprocessor.

89. The system of claim 88, wherein the microprocessor is operably connected with the processor.

90. The system of claim 88, wherein the microprocessor is configured to compute a predicted movement of the actuator.

91. The system of claim 75, wherein the robot comprises a network sensor configured to sense one or more of presence and strength of a network.

92. The system of claim 91, wherein the processor comprises the network sensor.

93. The system of claim 91, wherein the network sensor is configured to sense presence of a wireless network.