Solving MILP ( Yalmip ) with obstacle avoidance constraint

[Minh-Dang Nguyen]

Hello Dr. Johan,

I am currently working on a project regarding robust mpc with obstacle avoidance constraints. I did a robust mpc approach with constraint tightening and tube-based but I am not sure how to approach with obstacle avoidance constraints using mixed-integer LP. Also, I am not sure about MILP also and was wondering if you can give me some guidelines on how to start. Thank you and have a good day 

[Johan Löfberg]

not sure what the question is. obstacle avoidance in its basic form is just super hard as it leads to nonconvex models due to norm(x-y,inf)>=r  and similar constraints

[Minh-Dang Nguyen]

Hello Dr. Johan,

I mean that is it possible to add obstacle avoidance constraints within Yalmip using MILP (please see attached picture )? I am trying to add some obstacle avoidances constraints to the optimization problem but not sure how to start. Another file is the robust tightened constraints that I did. Thank you 

[Johan Löfberg]

you either do it low-level manually, essentially implementing if-else with 4 binary variables and associated binary variables

https://yalmip.github.io/modellingif

or you simply write norm([x;y]-center,inf) >= r (possibly rescaled if xmax-ymin and ymax-ymin aren't the same) and the MILP model is automatically derived

[Johan Löfberg]

i.e. [implies(d1,x>=xmax) , implies(d2,x<=xmin) , implies(d3,y>=ymax) , implies(d4,y<=ymin, d1+d2+d3+d4 == 1]

[Johan Löfberg]

and it sounds like you are implementing an example from here

https://yalmip.github.io/Work-shop/

[Minh-Dang Nguyen]

Hello Dr. Johan,

Thanks. Can you explain to me about the "implies" and "d1,d2,d3,and d4" , I am not sure what it means.  And what is the  norm([x;y]-center,inf) >= r for . I mean that I want to do a receding horizon MPC of a fixed length with obstacle avoidance constraints. do I have to define a rectangular box as polyhedron first and define my vehicle's position and how it is going to implement into the optimization problem? Thank you 

[Minh-Dang Nguyen]

I am trying to do some simulations closely related  to the attached picture

[Minh-Dang Nguyen]

Thanks for the examples. I mean that from my controller above, is there a way that I can add obstacle avoidance constraints using MILP? What are the steps I need to do? Please let me know your suggestion thank you  

On Tuesday, October 20, 2020 at 4:07:30 PM UTC-5 Johan Löfberg wrote:

[Johan Löfberg]

I've given you code that does precisely that.

implies defines a logical constraint "if binary d is true then the constraint X should hold" is implies(d1,X)

https://yalmip.github.io/command/implies/

norm(x-center,inf)<=r defines a box centered around center with radius r.

x = sdpvar(2,1);

clf

hold on

for i = 1:10

 Box = norm(x-randn(2,1)*10,inf)<= rand(1);

 plot(Box);

end

and thus a collision avoidance constraint to have x{k} avoid going into a box centered at z is norm(x{k}-z,inf) >= r

[Dang Nguyen]

Thank you, Dr. Johan, I am still trying to understand the concept of MILP using binary variables. So if I use the  norm(x-center,inf)<=r, then I actually don't have to define decision variables as binary for MILP? And for the obstacle avoidance constraints, can I have more than one? And is there a way that i can define a target point ( waypoint ) that my vehicle is trying to get there while avoiding those boxes?  Thank you 

[Johan Löfberg]

norm(.,inf) and norm(.,1) are MILP representable when used in a nonconvex way, and YALMIP automatically derives those MILP models

You can use the operators as many times as you want, but of course the more nonconvex constraints you have the the more binary variables will be introduced and he harder the problem will be. These problems become intractable very quickly

You can of course have "target points" you just have to come up with a way to introduce tem (penalty or equality on terminal state would be the standard approach, but it is what ever you want)

[Dang Nguyen]

Can you explain to me about the penalty or equality on terminal state ? It is similar to the terminal constraint that we want to drive our states to the origin but now we want to drive to a certain target? Thank you 

[Johan Löfberg]

If you want x to go to some particular point c, you would for instance add a penalty on x{k}-c for all states, or just on final state so x{N}-c, and what penalty you add is up to what kind of model you want, you might ant to use a LP-representable such as norm(x{k}-c,1) or maybe a quadratic penalty (x{k}-c)'*(x{k}-c)

or maybe just add the constraint that x{N} must be in some region

or from you pictures, it looked like you wanted the first element of the state to go to the right, so maybe just add the penalty on -x{N}(1), or use a slack s>=0 and add s (or s^2 or 10000*s^2 or what ever) with the constraint c<=x{N}(1)+s to ensure you only add a cost when x hasn't  reached the region. etc etc etc

[Dang Nguyen]

Thanks. For the   (x{k}-c)'*(x{k}-c)  , the point c  (r_{k}) is   define just a single (x,y) coordinate  in 2-d plot ? because I am defining in sdpvar something like objective = objective + (x_{k}-r_{k})'*Q*(x_{k}-r_{k}) which x_{k}= r_{k} (please see attached pic) ?  And  for the x{N} is terminal constraint ? because I have " constraints = [constraints, x_{N+1} == 0]" as of right now to drive state to the origin .  Thank you 

[Johan Löfberg]

c is just a generic for what ever you want the states to go to (be it 0 as your terminal state constraint tries to force it to (dangerous, what if it is impossible to reach zero within the prediction horizon) or r_k which you use in the stage cost

these thngs are just completely arbitrary tunings stuff, you use what ever give you the desired behavior and makes sense from the application

this whole discussion is completely unrelated to the topic: how to add nonconvex avoidance onstraints. the answer to that is that you either model it manually by adding all the logic constraints, or you use built-in stuff like nonconvex norm constraints

[Johan Löfberg]

and note, for the nonconvex MILP representations to work, all variables involved (i.e. x) have to be explitly bounded in the model. Otherwise the modelling engine will complain and scream at you that you have unbounded variables in stuff that are modelled using big-M models

[Dang Nguyen]

Thank you Dr. Johan 

[Dang Doan]

Hello Dr.Johan,

If I want to model the nonconvex avoidance constraints manually,  do I need to send it to a specific solver like Gurobi to solve the problem? And what do you prefer? Is there any advantage of doing it manually or use the built-in within yalmip ? Is there a big difference in results? 

Thanks 

[Johan Löfberg]

If the objects you are avoiding are polyhedral, the model will require the introduction of binary variables, you will need a solver which supports that (such as gurobi)

The only benefit of doing it manually is that you know exactly what you get and if there are some special structure that can be exploited, you can do that. The drawback is of course that you with 99% probability simply reinvent the wheel, miss some tricks done inside YALMIP, and low-level modelling easily introduces mistakes

[Dang Doan]

Hello Dr. Johan, 

And for the built-in nonconvex norm constraints in YALMIP, what are the objects that we are avoiding considered as? In other words, what are those rectangular boxes represented? 

it is just a region or dangerous area that are we trying to avoid and not a polyhedral set? 

Thanks 

[Johan Löfberg]

that depends on what you are modelling. you call them obstacles apparently 

[Dang Doan]

Hello Dr.Johan,

What is the difference between if you considered the objects to be polyhedral set or real obstacles? It is like an approximation that the obstacles bounded within the polyhedral set if we considered what are we avoiding are polyhedral? 

Thanks  

[Johan Löfberg]

??

everything is about models so asking what the difference is between a polyhedral set and the real object is really strange.

you have reality, and then you have a model of reality

[Dang Doan]

Sorry for the confusion. I mean that I am confused about the polyhedral set, I am not sure what the set represented as an obstacle. Why do we consider the object we avoiding as polyhedral rather than a real object?

Thanks 

[Johan Löfberg]

if you are trying to avoid a car, how do you physically put a real car into your computer and what kind of weird programming language do you use which can physically interact with that car to somhow come up with a control strategy to avoid these things

*everything* is represented by models when you program. talking about the real object makes no sense

[Dang Doan]

Understood, thank you, Dr. Johan.  For the objects that we are avoiding are polyhedral, why do we need to introduce binary variables? Can we use the built-in nonconvex norm constraint within YALMIP to solve? 

Thank you 

[Johan Löfberg]

norm(x,inf) >= r means (x(1) >= r or x(1) <= -r or x(2) >=r or x(2) <=--r or ...) which is nonconvex but at the same time also obviously a logic constraint over linear conditions, and logics with linear stuff is MILP-representable and yalmip derives that MILP model

[Dang Doan]

So if the objects we are avoiding are polyhedral,  can we use the norm(x,inf) >=r also rather than introduce the binary variables for the model? 

Thanks 

[Johan Löfberg]

yes, yalmip automatically derives the MILP model when you use LP-representable norms and operators in a nonconvex way