# 2D Path Planning with Minkowski and OpenSCAD

CS 480: Robotics & 3D Printing Lecture, Dr. Lawlor

When doing path planning in 2D for a ground robot, we often work in 3D so we can explicitly represent the robot's orientation.  The Z axis units might be degrees, from 0 (robot facing forward) through 180 (robot facing backward) to 360 again (robot facing forward again).  This does mean the +Z and -Z faces wrap around.

Given a simple room shape, and a disk shaped robot, the configuration space is very simple, with the walls inset by the robot's radius.  For a more complicated robot shape, the allowable distance from the walls depends on the robot's orientation, which makes the allowed region in configuration space more complex.

It's possible to use OpenSCAD's minkowski sum to compute the allowed region of the robot center in this 3D configuration space.

The rationale here is:
• We start with a 2D outline of the robot.  Here we're assuming a rectangular outline (actually the dimensions of our NASA mining robot, 150cm x 75cm).
• We use a linear_extrude with a 360 degree helical twist to explicitly represent the robot's shape at each orientation in configuration space.  This is shown in red below.
• We'd like to compute the region of configuration space where the robot's center point can be, while keeping the robot from touching any of the walls.  This is shown in blue below.  The straight walls have become scalloped due the robot's changing size in different orientations.

`/**  Robot 2D path planning in OpenSCAD    Dr. Orion Lawlor, lawlor@alaska.edu, 2015-10-04 (Public Domain)*/// Number of orientations to check:turn_slices=8; // every 45 degrees, under 1 minute// turn_slices=36; // every 10 degrees, 3 minutes// Robot 2D outline, mirrored on both axesmodule robot_2D() {    square(size=[150,75],center=true);}// Robot's 3D configuration space outlinemodule robot_3D() {    linear_extrude(height=360,twist=-360,convexity=8,slices=turn_slices) robot_2D();}// Outline of roommodule room_2D() {    difference() {        translate([-378/2,0,0])            square(size=[378,738]);        // projecting hole in room         //translate([0,300])        //    square(size=[500,200]);    }}// Difference between environment and roommodule room_disallowed() {    difference() {        translate([-300,-100,0])            square(size=[600,1000]);        room_2D();    }}// Disallowed region for robot center pointmodule robot_disallowed() {    minkowski() {        robot_3D();        linear_extrude(height=1)            room_disallowed();    }}// Allowed region for robot center pointmodule robot_allowed() {    difference() {        linear_extrude(height=360,convexity=2) room_2D();        robot_disallowed();    }}robot_3D();robot_allowed();`
`	cat foo.stl | grep vertex | awk '{printf("  vertex(%.3f,%.3f,%.3f);\n",\$2,\$3,\$4);}' > foo.js`