Motion planning

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.

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.