Yalmip for fitting polynomial

[Mohamed Soliman]

Hello Johan

If I have a path that I generated from a planner and I want to fit this path with a polynomial and additionally I want this fitting to respect some constraints ( i will use also binary variable to express some constraints)  how can Yalmip help me doing so.

BR

Mohamed 

[Johan Löfberg]

https://yalmip.github.io/example/polynomialdesign/

[Mohamed Soliman]

Thanks a lot for your reply 

I am following the link that you sent, but I am still wondering how can I express the constraints in the fitting if I have for examples obstacles (kindly, see my attached figure) I can fit this path with an approximated 5 th order polynomial but of course this approximated path hit the constraints. I have uploaded the m.file surly there is something that I still miss understand 

Again many thanks for your help and support

BR

Mohamed

[Johan Löfberg]

unclear what you are doing. 

you reference a data file which isn't attached. 

you show a picture in 2D, but appear to have a polynomial in 1D. 

you define x as a constant and then as an sdpvar immediately after

replace(p,x,x) makes no sense.

avoidance constraint of a box can never be one with a single linear inequality which you appear to have

[Mohamed Soliman]

Hello Johan

The reference data is attached 

the picture is just to illustrate the problem ( this path is already planned and I want to find a polynomial that can approximately fit the path without hitting the obstacles)

I was trying to define the box with binary variable (maybe I am wrong)

All the best

[Johan Löfberg]

my other questions remain

E.g., to define an obstacle, you must somehow have the model to_the_left OR to_the_right OR above OR below. That cannot be the case with your current model. A big-M representation would require 4 linear equalities per box + 1 disjunction on the 4 binaries related to that box

[Johan Löfberg]

but better is that you use the built-in functions and simply use

norm(replace(x,t,t_i) - box_center,inf) >= box_size

I assume you have x as a 2d polynomial parameterized in a variable called t, sampled at instances t_i

[Mohamed Soliman]

Hello Johan,

I have updated the code :

- I have  considered the box centers and box sizes 

- x is given in line 10

The problem is given these data points (in line 10) I want to find a poly coefficients that yield y=f(x) such that when I plot x-y path , the resulting path does not hit with the boxes.

And again I am sorry if my question was not clear or if can not see what you are trying to explain I am still in my first steps using Yalmip 

BR

Mohamed  

[Johan Löfberg]

Code makes no sense

x=xhist(1,:);

x = sdpvar(1);

First line is redundant, as you overwrite that variable immediately

[p,a,v] = polynomial(x,6);

Why are you definig a scalar polynomial, when the path is in 2D? OK, I see you want y(x), but when moving in 2D, it is much much more natural to have {x(t),y(t)}. Otherwise it is impossible to go straight down  (as your path appears to want to do), or move to the right and down and then turn around and go left and down

You define p but never use it

 norm(replace(y,x,t_i) -

What is y, it is not defined. There is no variable called t_i either

[Johan Löfberg]

xdata = xhist(1,:);

ydata = xhist(2,:);

sdpvar t

[x,a] = polynomial(t,5);

[y,b] = polynomial(t,5);

objective = 0;

t_i = linspace(0,1,length(xdata));

X = [];

Y = [];

for i = 1:length(xdata)

    x_i = replace(x,t,t_i(i));X = [X x_i];

    y_i = replace(y,t,t_i(i));Y = [Y y_i];

    objective = objective + (x_i-xdata(i))^2 + (y_i - ydata(i))^2;

end

Match = [X(1)==xdata(1),

         X(end)==xdata(end),

         Y(1)==ydata(1),

         Y(end)==ydata(end)]

optimize(Match,objective);

plot(value(X),value(Y))

hold on

plot(xdata,ydata)

torsdag 16 september 2021 kl. 11:31:12 UTC+2 skrev mosoli...@gmail.com:

[Johan Löfberg]

load safe_path

xhist = xhist(:,1:10:end);

xdata = xhist(1,:);

ydata = xhist(2,:);

sdpvar t

[x,a] = polynomial(t,5);

[y,a] = polynomial(t,5);

objective = 0;

t_i = linspace(0,1,length(xdata));

X = [];

Y = [];

Avoid = [];     

for i = 1:length(xdata)

    x_i = replace(x,t,t_i(i));X = [X x_i];

    y_i = replace(y,t,t_i(i));Y = [Y y_i];

    objective = objective + (x_i-xdata(i))^2 + (y_i - ydata(i))^2;

    Avoid = [Avoid, norm([x_i;y_i] - [50;50],inf) >= 20];

end

Match = [X(1)==xdata(1),

         X(end)==xdata(end),

         Y(1)==ydata(1),

         Y(end)==ydata(end)];

optimize([Match,Avoid],objective);

plot(value(X),value(Y))

hold on

plot(xdata,ydata)

sdpvar z(2,1);

plot(norm(z-[50;50],inf)<=20)

    

torsdag 16 september 2021 kl. 11:31:12 UTC+2 skrev mosoli...@gmail.com:

[Mohamed Soliman]

Hi Johan

Thanks a lot for your help

BR

Mohamed 

[Mohamed Soliman]

Hello Johan

One more question if you do not mind 

I have added all constraints I have. 

Now,If I want to enforce the function to be at a certain point near the big red box, I used for that( Y(55)==ydata(55) in the line in 34 but the problem does not converge 

[Johan Löfberg]

https://yalmip.github.io/slowmilp

However, I am not sure adding such a constraint makes sense. If you for instance solve the problem and replace the objective with abs(Y(55)-ydata(55)) it will return a solution which satifies this, but as you will see, the path is completely arbitrary, in other words "y at index 55" has no meaning really once you are parameterized in the path variable. Sure you are using the path deviation in objective which sort of keeps you connected to the initial parameterization but vague. In other words, if it is important that the solution passes close to (xdata(55)-ydata(55)) you will have to model when x close to xdata(55) then y close to ydata(55) which I am not sure how it is done easily working in a path parameter. penalizing (X;Y)(55)-(xdata;ydata)(55) strongly is one hack

[Mohamed Soliman]

Should the objective of minimizing the difference between data points and x_i yield a function that is somehow near the original data,i.e. the fitted data should be near to big box?

even by giving more weights, this does not help

[Johan Löfberg]

That code does not even run

Scaling the objective with 1000 (or what ever) makes absolutely no difference

Polynomials are simply bad interpolants

[Mohamed Soliman]

So we do you suggest to fit the data such that the interpolated data avoid the obstacle and in the same time be near the big box

many thanks for your patience