Syntactic inferential motion planning method for robotic systems

• US 20070005179A1
• Filed: 01/30/2004
• Published: 01/04/2007
• Est. Priority Date: 01/31/2003
• Status: Active Grant

• Current Assignee: Thermo CRS Ltd. (Thermo Fisher Scientific Incorporated)
• Original Assignee: Thermo CRS Ltd. (Thermo Fisher Scientific Incorporated)
• Inventors: Johnson, Stephen, Mccrackin, Daniel
• Granted Patent: US 9,855,657 B2
• Time in Patent Office: Days
• US Class Current: 700/213
• CPC Class Codes: B25J 9/163 learning, adaptive, model based, rule based expert control
• CPC Class Codes: B25J 9/1666 Avoiding collision or forbidden zones
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

A method and system for planning and optimizing the movement of a robotic device comprises establishing a plurality of spatial locations where the device can possibly be positioned and establishing rule sets for constraining movement of the robotic device between the locations. Once a start and end point have been determined, the method of the invention calculates all possible routes for the device to move, via the established locations and following the constraints of the rule sets. The calculated routes are then compared to a criteria, such as minimizing time, and an optimum route, meeting the desired criteria is determined. The calculated routes may also be cached for future access. The invention also provides for an error recovery method for allowing a robotic device to recover should it encounter an error.

Claims

1. A method of planning motion of a robot from a start location to an end location, said start and end locations being within the range of motion of said robot, the method comprising:

a) defining at least two locations in terms of a spatial coordinate system, said at least two locations including said start and end locations;

b) storing said at least two locations in a computer memory;

c) defining a set of rules for governing movement of said robot between said at least two locations;

d) storing said set of rules in the computer memory;

e) calculating possible routes, through said at least two locations, from said start location to said end location; and

f) determining from said possible routes an optimized route which meets a predetermined criteria.

2. The method of claim 1 wherein said at least two locations include a plurality of locations between said start and end locations.

3. The method of claim 1 wherein said at least two locations include a plurality of possible locations of said robot.

4. The method of claim 1 wherein said set of rules comprises conditions of movement of said robot between adjacent pairs of said locations.

5. The method of claim 1 wherein, in step (e), all possible routes between said start and end locations are calculated, said routes comprising a sequence of locations.

6. The method of claim 1 wherein, in step (f), the predetermined criteria comprises a minimized travel time of said robot between said start and end locations.

7. The method of claim 1 wherein said rules comprise at least one path, said path comprising two or more of said at least two locations arranged in a preset order and wherein movement of said robot between locations on said paths is constrained to said preset order.

8. The method of claim 1 wherein said rules comprise at least one region, said region comprising two or more of said at least two locations arranged in a grouping and wherein said robot is permitted to move freely between any locations within said grouping.

9. The method of claim 1 wherein said rules comprise at least one path and at least one region, said path comprising two or more of said at least two locations arranged in a preset order and wherein movement of said robot between locations on said paths is constrained to said preset order, and said region comprising two or more of said at least two locations arranged in a grouping and wherein said robot is permitted to move freely between any locations within said grouping.

10. The method of claim 9 wherein, in step (e) of the method, all possible routes between said start and end locations are calculated, said routes comprising a sequence of locations.

11. The method of claim 10 wherein, in step (f), the predetermined criteria comprises a minimized travel time of said robot between said start and end locations.

12. The method of claim 2 wherein said at least two locations are chosen from the group comprising:

object engagement or release positions of said robot;

safe positions of said robot; and

transit positions of said robot.

13. The method of claim 3 wherein said at least two locations are chosen from the group comprising:

object engagement or release positions of said robot;

safe positions of said robot; and

transit positions of said robot.

14. The method of claim 6 wherein said step (f) comprises the sub-steps of:

i) finding all minimum-length routes that take the robot from the start location to the end location; and

,

ii) choosing from said minimum-length routes of step (i), the route having the shortest travel time from said start location to end location.

15. The method of claim 1 wherein said method includes an error resolving algorithm wherein the robot is capable of resolving its location when an error condition is encountered.

16. The method of claim 15 wherein said error resolving algorithm results in the robot being assigned to a nearest one of said at least two locations.

17. The method of claim 16 wherein the robot is assigned to the nearest one of said locations by the steps of:

a) choosing a minimum distance limit;

b) calculating the distance of said robot from each of said at least two locations;

c) identifying the nearest location to said robot, said nearest location having the shortest distance from said robot;

d) comparing said shortest distance to said distance limit; and

e) where said shortest distance is less than or equal to said distance limit, assigning the robot to said nearest location.

18. The method of claim 9 wherein said method includes an error resolving algorithm wherein the robot is capable of resolving its location when an error condition is encountered.

19. The method of claim 18 wherein said error resolving algorithm results in the robot being assigned to a nearest one of said at least two locations.

20. The method of claim 19 wherein the robot is assigned to the nearest one of said locations by the steps of:

a) choosing a minimum distance limit;

b) calculating the distance of said robot from each of said at least two locations;

c) identifying the nearest location to said robot, said nearest location having the shortest distance from said robot;

d) comparing said shortest distance to said distance limit; and

e) where said shortest distance is less than or equal to said distance limit, assigning the robot to said nearest location.

21. The method of claim 20 wherein, where said shortest distance of step (e) is more than said distance limit, the method further comprising the steps of:

f) assigning a weighting factor, M, to each path and region;

g) calculating the shortest distance, D, from the robot to each line joining said at least two locations in said paths and regions;

h) dividing said shortest distances by the weighting factor to provide weighted distances, D/M;

i) identifying the line segment with the smallest weighted distance D/M;

j) comparing the smallest weighted distance, D/M, of step (i) with said minimum distance limit;

k) if the weighted distance for the identified line segment is less than the minimum distance limit, assigning the robot to said identified line segment;

l) calculating the distance of the robot to the end points of said identified line segment;

m) moving said robot to the closest of said end points and assigning the robot to the location occupied by the closest of said end points.

22. The method of claim 18 wherein said error resolving algorithm comprises the steps of:

a) choosing a minimum distance limit;

b) assigning a weighting factor, M, to each path and region;

c) calculating the shortest distance, D, from the robot to each line joining said at least two locations in said paths and regions;

d) dividing said shortest distances by the weighting factor to provide weighted distances, D/M;

e) identifying the line segment with the smallest weighted distance D/M;

f) comparing the smallest weighted distance, D/M, of step (e) with said minimum distance limit;

g) if the weighted distance for the identified line segment is less than the minimum distance limit, assigning the robot to said identified line segment;

h) calculating the distance of the robot to the end points of said identified line segment;

i) moving said robot to the closest of said end points and assigning the robot to the location occupied by the closest of said end points.

23. The method of claim 9 wherein said step (f) comprises the sub-steps of:

i) finding all minimum-length routes that take the robot from the start location to the end location; and

ii) choosing from said minimum-length routes of step (a), the route having the shortest travel time from said start location to end location.

24. The method according to claim 1 wherein optimized routes between pairs of locations are cached in the computer memory and made searchable.

25. The method of claim 24 wherein, upon entering a start location and an end location, the computer memory is searched for previously determined optimized paths.

26. A controller for a robot encoding the method of claim 1.

27. An error correction method for correcting the positioning of a robot, the method comprising the steps of:

a) defining a plurality of possible locations of the robot in terms of a spatial coordinate system;

b) choosing a minimum distance limit;

c) calculating the distance of said robot from each of said locations;

d) identifying the nearest location to said robot, said nearest location having the shortest distance from said robot;

e) comparing said shortest distance to said distance limit; and

f) where said shortest distance is less than or equal to said distance limit, assigning the robot to said nearest location.

28. The method of claim 27 wherein, where said shortest distance of step (f) is more than said distance limit, the method further comprising the steps of:

g) choosing a weighting factor, M;

h) calculating the shortest distance, D, from the robot to each line joining pairs of said locations;

i) dividing said shortest distances by the weighting factor, M, to provide weighted distances, D/M;

j) identifying the line segment with the smallest weighted distance D/M;

k) comparing the smallest weighted distance, D/M, of step (j) with said minimum distance limit;

l) if the weighted distance for the identified line segment is less than the minimum distance limit, assigning the robot to said identified line segment;

m) calculating the distance of the robot to the end points of said identified line segment;

n) moving said robot to the closest of the said end points and assigning the robot to the location occupied by the closest of said points.