In this workshop we will work on the solution to the shortest path problem assigned a few weeks ago.

The purpose of the assignment was to demonstrate:

1. That there are a variety of curves that could pass through n points and that it is important to have an objective in choosing the appropriate curve. In this case there are two objectives:
1. Smooth curves,  so the robot is not subjected to jerking motion
2. Shortest curve, so the robot can pass the points most efficiently
2. That working with splines requires handling a piecewise function. In this case the integration must be done piecewise.

This problem involves interpolation and calculus, so a good tool is Maxima, which has the ability to do both Lagrangian Interpolation and Cubic Splines plus the ability to find the derivatives and do the necessary integration.

Maxima is available for installation on a Windows PC as wxMaxima (download here), but we will use the online version at http://www.maxima-online.org. Click on that link to bring up the online Maxima calculator in a new window, then cut an paste the code below into the Instructions toMaxima box. Clicking on Calculate will then do all the work and reveal that splines, while more complicated, produce a shorter path for the robot. (What % reduction in the length is noted?)

To complete the assignment, repeat the calculation with the following (x,y) data, then send an e-mail to math@sjut.org containing:

1. Name & Registration Number
2. (x,y) data
3. Brief comparison of the two path lengths and the shape of the curves – remembering the objective.
4. The plot of the paths (either “Copy Image” and paste into the email or “Save Image As” and attach to the email).

(x,y) data

``````
[2,4],[4,5],[5,6],[6,3],[8,2],[10.6,5]
``````

Maxima script to calculate the lengths:

``````/* Enter the data */
A:matrix([2,7.2],[4.5,7.1],[5.25,6],[7.81,5],[9.2,3.5],[10.6,5]);
kmax:length(A)-1\$
x0:lmin(list_matrix_entries(submatrix(A,2)))\$
x1:lmax(list_matrix_entries(submatrix(A,2)))\$
/* Nth order polynomial using Lagrangian interpolation */
f_nth: lagrange(A)\$
df_nth: sqrt(1+(diff(f_nth,x)^2))\$
L_nth:romberg(df_nth,x,x0,x1);
/* Cubic spline interpolation */
/* Calculate the splines */
f_cs:cspline(A)\$
/* Pull out the cubic polynomial for each subinterval */
h1[i,j]:=1\$
L_splines:0\$
f_splines: matrix()\$
for k:1 thru kmax do
(   kill(h2,h3),
h2[i,j]:=A[k,1]+(i-1)/3*(A[k+1,1]-A[k,1]),
h3[i,j]:=ev(f_cs,x=C2[i,1]),
C1:genmatrix(h1,4,1), C2:genmatrix(h2,4,1), C3:C2^2, C4:C2^3,
D:genmatrix(h3,4,1),
aCS:invert(C).D,
f_spline:matrix([1,x,x^2,x^3]).aCS,