Knitro for a sequence of motion planning problems: improve initial guess

[tim....@gmail.com]

Dear all

I am currently trying out Knitro to solve motion planning problems: a holonomic vehicle moves from A to B and has to avoid all (moving) obstacles in the environment, while respecting its velocity bounds and minimizing its motion time.
Since the environment may change, I solve the problem with a receding horizon. So after the vehicle has moved for a specific time (being the time step), the information about the vehicle position, obstacle positions, velocities,... is updated. This leads to a new problem, which is very similar to the previous one since the main difference is that the starting point has shifted a bit. Therefore, the previous trajectory is used as an initial guess.

I am currently solving this NLP with Knitro with the following options (based on: https://groups.google.com/forum/#!topic/knitro/pNLLVsh9BmI):
    bar_initpt=2
    honorbnds=0
    scale=1 (they suggest scale=0, but with scaling works better for me)

With these options I could decrease the computation time for an easy example with a factor 2.5, compared to IPOPT.

Now I have two questions:

1) I tried to change more things, but I am a bit lost in the big amount of options which can be set. Therefore, I was wondering if you have any further advice which options I could try to further decrease the computation time?

2) Because the subsequent problems are very similar I was thinking that the active set method should work best. Although, for my example the interior point method is still faster... Therefore, I was wondering if it is possible to give an initial guess of the active set? Normally the active set over subsequent problems will be (almost) the same, so I guess passing the active set will make things faster.

Thanks in advance!

Kind regards,

Tim

[Richard Waltz]

Dear Tim,

We agree the number of options in Knitro can be a bit overwhelming.  We are working to try to provide better guidance in the documentation about which options usually have the biggest effect.  Minimally you should try all the algorithms (and you can run them all in parallel).  One other thing I highly recommend is to use the Knitro Tuner - see:

https://www.artelys.com/tools/knitro_doc/2_userGuide/tuner.html

The easiest way to run the default Tuner is to set "tuner=1".  Then Knitro will run with a variety of option settings (focusing on the most important options) and report some summary statistics about which non-default option settings may help on your model.  You can also customize the tuning process by explicitly specifying which options you want to tune over.

Regarding your second question - yes, if you are solving a sequence of similar problems, then the active-set method may be preferable, provided your models are not too large.  Unfortunately, we do not yet offer a way for you to feed an initial guess of the active-set to Knitro.  However you can provide an initial point (and initial Lagrange multiplier estimates).  When solving a sequence of closely related problems, if you take the solution of the previous problem and feed it as the initial point for the next problem, this generally should speed up the optimization.

Please let us know if you have further questions.  We can also investigate further, if you send us your models offline.

Best,

Richard WALTZ

Senior Scientist

 

Artelys USA

 

---

From: kni...@googlegroups.com [kni...@googlegroups.com] on behalf of tim....@gmail.com [tim....@gmail.com]
Sent: Tuesday, September 20, 2016 1:43 AM
To: Artelys Knitro forum
Subject: [Knitro] Knitro for a sequence of motion planning problems: improve initial guess

--
You received this message because you are subscribed to the Artelys "Knitro Nonlinear Optimization Solver" google group.
To post to this group, send email to kni...@googlegroups.com
To unsubscribe from this group, send email to knitro-un...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/knitro?hl=en
Thank You,
Artelys
http://www.artelys.com/en/optimization-tools/knitro
---
You received this message because you are subscribed to the Google Groups "Artelys Knitro forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to knitro+un...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Tim Mercy]

Dear Richard

Sorry for my very late answer, but I could only look at your advice today...

I already tried the Knitro Tuner, that's when I found out that the IP method ran faster than the AS method. But I will play maybe play with it a little more to find out if I can speed things up.

I already provided an initial guess for the variables, but it is indeed a good idea to also provide a guess for the Lagrangian multipliers! Feeding an initial guess for the active set would be a very nice feature. If you like, I can send you my models! Do you only work with the AMPL format, or can I also send you my original problem (modeled with CasADi)?

Thank you for your advice!

Kind regards,

Tim Mercy

Op dinsdag 20 september 2016 17:32:52 UTC+2 schreef Richard Waltz:

[Richard Waltz]

Hi Tim,

Thanks for the feedback.  Yes, if you can send us your model, we'll try to take a look at it when we have time.  This could be helpful for us in exploring the "warm-start" issue (when solving a sequence of closely related problems).  AMPL models are definitely our preference, if possible, but we'll take the model in whatever form you are able to provide it.

Best,
-Richard

Richard WALTZ

Senior Scientist

 

Artelys USA

 

---

From: Tim Mercy [tim....@gmail.com]
Sent: Monday, October 31, 2016 9:26 AM
To: Artelys Knitro forum
Cc: Richard Waltz
Subject: Re: [Knitro] Knitro for a sequence of motion planning problems: improve initial guess