Granted Patent B2

US 12,649,237 · App. 18/269,325 · Granted Jun 9, 2026

Inventors: Øystein Hov Holhjem (Oslo, NO); Gudbrand Eggen (Oslo, NO); Torstein Anderssen Myhre (Oslo, NO)

Assignee: ZIVID AS

B25J9/1666B25J9/163

Abstract

Claims (47)

1 . A method of generating a path for a robot, wherein the robot is arranged to operate between a plurality of states in a workspace, said workspace being represented by a plurality of discretized workspace elements, wherein each of said states is connected to at least one other state via at least one respective transition, wherein the method comprises:

generating or receiving a first model;

determining a first set comprising one or more workspace elements that are at least partially in collision with the first model for each of the plurality of states and the respective transition(s) between those states;

generating a first mapping comprising information regarding said first set and the respective plurality of states and respective transition(s) for which the first model is at least partially in collision with the respective workspace elements in the first set, and storing said first mapping in a first memory area;

generating or receiving a second model that extends from the first model;

determining a second set comprising one or more further workspace elements, additional to those in the first set, that are at least partially in collision with the second model for each of the plurality of states and the respective transition(s) between those states; and

generating a second mapping comprising information regarding said second set and the respective plurality of states and respective transition(s) for which the second model is at least partially in collision with the respective workspace elements in the second set, and storing said second mapping in a second memory area;

combining at least the first and second mappings to provide the path; and

outputting the path to the robot, the path comprising instructions for moving the robot.

2 . The method as claimed in claim 1 , wherein the first model comprises a representation of a first link of the robot.

3 . The method as claimed in claim 1 , wherein the second model comprises a representation of a second link of the robot.

4 . The method as claimed in claim 1 , further comprising:

generating or receiving an additional model that extends from at least one of the first or second models;

determining an additional set comprising one or more further workspace elements, additional to those in the first and second sets, that are at least partially in collision with the additional model for each of the plurality of states and the respective transition(s) between those states; and

generating an additional mapping comprising information regarding said additional set and the respective plurality of states and respective transition(s) for which the additional model is at least partially in collision with the respective workspace elements in the additional set, and storing said additional mapping in an additional memory area.

5 . The method as claimed in claim 4 , wherein the additional model comprises a representation of an additional link of the robot.

6 . The method as claimed in claim 1 , wherein the step of determining the set of workspace elements at least partially in collision with each model comprises checking the states and transitions that are allowed by the respective dimension of movement afforded by said model.

7 . The method as claimed in claim 1 , wherein the step of determining the set of workspace elements at least partially in collision with each model comprises checking the states and transitions for collisions with a static obstacle and/or for self-collisions.

8 . The method as claimed in any preceding claim , wherein the first and second memory areas are each within a memory.

9 . The method as claimed in claim 1 , further comprising removing one or more workspace elements from the second set that are in first set.

10 . The method as claimed in claim 1 , wherein one or more workspace elements that are at least partially in collision with more than one of the models are included in the sets corresponding to each of said models.

11 . The method as claimed in claim 1 , wherein one or more workspace elements that are at least partially in collision with more than one of the models are included in the set corresponding to only one of said models.

12 . The method as claimed in claim 1 , comprising generating a base mapping comprising information regarding one or more workspace elements that are at least partially in collision with a static part of the robot.

13 . The method as claimed in claim 1 , wherein the information stored for one or more of the mappings may comprise a plurality of points of interest.

14 . The method as claimed in claim 1 , comprising discretizing the workspace into workspace elements of different shapes and/or sizes.

15 . The method as claimed in claim 1 , wherein one or more of the models is at least partially axially symmetric, the method comprising storing information regarding the workspace elements partially occupied identically for multiple rotational states in a mapping for that model only once.

16 . The method as claimed in claim 1 , wherein only workspace element information relating to workspace elements at least partially in collision with the first and/or second model and the corresponding states and/or transitions that result in the collisions for one direction of a transition are stored in the corresponding set.

17 . The method as claimed in claim 1 , wherein only the workspace element information relating to workspace elements at least partially in collision with the first and/or second model and the corresponding states and/or transitions that result in the collisions for a transition that are not found in any of the states to which said transition connects are stored in the corresponding set.

18 . The method as claimed in claim 1 , wherein workspace element information relating to workspace elements at least partially in collision with the first and/or second model and the corresponding states and/or transitions that result in the collisions that correspond to combined movements are only stored for the higher links, while the simple transitions for the lower links are reused.

19 . A motion planning system arranged to generate a path for a robot, wherein the robot is arranged to operate between a plurality of states in a workspace, said workspace being represented by a plurality of discretized workspace elements, wherein each of said states is connected to at least one other state via at least one respective transition, wherein the motion planning system is arranged to:

generate or receive a first model;

determine a first set comprising one or more workspace elements that are at least partially in collision with the first model for each of the plurality of states and the respective transition(s) between those states;

generate a first mapping comprising information regarding said first set and the respective plurality of states and respective transition(s) for which the first model is at least partially in collision with the respective workspace elements in the first set, and store said first mapping in a first memory area;

generate or receive a second model that extends from the first model;

determine a second set comprising one or more further workspace elements, additional to those in the first set, that are at least partially in collision with the second model for each of the plurality of states and the respective transition(s) between those states; and

generate a second mapping comprising information regarding said second set and the respective plurality of states and respective transition(s) for which the second model is at least partially in collision with the respective workspace elements in the second set, and store said second mapping in a second memory area;

combine at least the first and second mappings to provide the path; and

output the path to the robot, the path comprising instructions for moving the robot.

20 . A non-transitory computer-readable medium comprising instructions that, when executed by a processor, cause the processor to carry out a method of performing motion planning generating a path for a robot, wherein the robot is arranged to operate between a plurality of states in a workspace, said workspace being represented by a plurality of discretized workspace elements, wherein each of said states is connected to at least one other state via at least one respective transition, wherein the method comprises:

generating or receiving a first model;

determining a first set comprising one or more workspace elements that are at least partially in collision with the first model for each of the plurality of states and the respective transition(s) between those states;

generating a first mapping comprising information regarding said first set and the respective plurality of states and respective transition(s) for which the first model is at least partially in collision with the respective workspace elements in the first set, and storing said first mapping in a first memory area;

generating or receiving a second model that extends from the first model;

determining a second set comprising one or more further workspace elements, additional to those in the first set, that are at least partially in collision with the second model for each of the plurality of states and the respective transition(s) between those states;

generating a second mapping comprising information regarding said second set and the respective plurality of states and respective transition(s) for which the second model is at least partially in collision with the respective workspace elements in the second set, and storing said second mapping in a second memory area;

combining at least the first and second mappings to provide the path; and

output the path to the robot, the path comprising instructions for moving the robot.

Assignments (2)

Priority Claims (1)

Continuity (1)

References Cited (14)