GCC Code Coverage Report


Directory: ./
File: src/core/solvers/fddp.cpp
Date: 2025-02-24 23:41:29
Exec Total Coverage
Lines: 137 172 79.7%
Branches: 129 462 27.9%

Line Branch Exec Source
1 ///////////////////////////////////////////////////////////////////////////////
2 // BSD 3-Clause License
3 //
4 // Copyright (C) 2019-2022, LAAS-CNRS, University of Edinburgh
5 // Heriot-Watt University
6 // Copyright note valid unless otherwise stated in individual files.
7 // All rights reserved.
8 ///////////////////////////////////////////////////////////////////////////////
9
10 #ifdef CROCODDYL_WITH_MULTITHREADING
11 #include <omp.h>
12 #endif // CROCODDYL_WITH_MULTITHREADING
13
14 #include "crocoddyl/core/solvers/fddp.hpp"
15 #include "crocoddyl/core/utils/exception.hpp"
16
17 namespace crocoddyl {
18
19 25 SolverFDDP::SolverFDDP(std::shared_ptr<ShootingProblem> problem)
20
1/2
✓ Branch 2 taken 25 times.
✗ Branch 3 not taken.
25 : SolverDDP(problem), dg_(0), dq_(0), dv_(0), th_acceptnegstep_(2) {}
21
22 62 SolverFDDP::~SolverFDDP() {}
23
24 16 bool SolverFDDP::solve(const std::vector<Eigen::VectorXd>& init_xs,
25 const std::vector<Eigen::VectorXd>& init_us,
26 const std::size_t maxiter, const bool is_feasible,
27 const double init_reg) {
28
3/16
✗ Branch 2 not taken.
✓ Branch 3 taken 16 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✓ Branch 15 taken 16 times.
✗ Branch 17 not taken.
✓ Branch 18 taken 16 times.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
16 START_PROFILER("SolverFDDP::solve");
29
1/2
✗ Branch 2 not taken.
✓ Branch 3 taken 16 times.
16 if (problem_->is_updated()) {
30 resizeData();
31 }
32 16 xs_try_[0] =
33 32 problem_->get_x0(); // it is needed in case that init_xs[0] is infeasible
34 16 setCandidate(init_xs, init_us, is_feasible);
35
36
1/2
✓ Branch 1 taken 16 times.
✗ Branch 2 not taken.
16 if (std::isnan(init_reg)) {
37 16 preg_ = reg_min_;
38 16 dreg_ = reg_min_;
39 } else {
40 preg_ = init_reg;
41 dreg_ = init_reg;
42 }
43 16 was_feasible_ = false;
44
45 16 bool recalcDiff = true;
46
2/2
✓ Branch 0 taken 50 times.
✓ Branch 1 taken 6 times.
56 for (iter_ = 0; iter_ < maxiter; ++iter_) {
47 while (true) {
48 try {
49
1/2
✓ Branch 1 taken 50 times.
✗ Branch 2 not taken.
50 computeDirection(recalcDiff);
50 } catch (std::exception& e) {
51 recalcDiff = false;
52 increaseRegularization();
53 if (preg_ == reg_max_) {
54 return false;
55 } else {
56 continue;
57 }
58 }
59 50 break;
60 }
61 50 updateExpectedImprovement();
62
63 // We need to recalculate the derivatives when the step length passes
64 50 recalcDiff = false;
65 50 for (std::vector<double>::const_iterator it = alphas_.begin();
66
1/2
✓ Branch 3 taken 52 times.
✗ Branch 4 not taken.
52 it != alphas_.end(); ++it) {
67 52 steplength_ = *it;
68
69 try {
70
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
52 dV_ = tryStep(steplength_);
71 } catch (std::exception& e) {
72 continue;
73 }
74
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
52 expectedImprovement();
75
2/4
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 52 times.
✗ Branch 5 not taken.
52 dVexp_ = steplength_ * (d_[0] + 0.5 * steplength_ * d_[1]);
76
77
2/2
✓ Branch 0 taken 39 times.
✓ Branch 1 taken 13 times.
52 if (dVexp_ >= 0) { // descend direction
78
7/8
✓ Branch 1 taken 39 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 31 times.
✓ Branch 5 taken 8 times.
✓ Branch 6 taken 30 times.
✓ Branch 7 taken 1 times.
✓ Branch 8 taken 38 times.
✓ Branch 9 taken 1 times.
39 if (std::abs(d_[0]) < th_grad_ || dV_ > th_acceptstep_ * dVexp_) {
79 38 was_feasible_ = is_feasible_;
80
5/6
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 33 times.
✓ Branch 2 taken 4 times.
✓ Branch 3 taken 1 times.
✓ Branch 5 taken 38 times.
✗ Branch 6 not taken.
38 setCandidate(xs_try_, us_try_, (was_feasible_) || (steplength_ == 1));
81 38 cost_ = cost_try_;
82 38 recalcDiff = true;
83 38 break;
84 }
85 } else { // reducing the gaps by allowing a small increment in the cost
86 // value
87
3/4
✓ Branch 0 taken 13 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 12 times.
✓ Branch 3 taken 1 times.
13 if (!is_feasible_ && dV_ > th_acceptnegstep_ * dVexp_) {
88 12 was_feasible_ = is_feasible_;
89
4/6
✓ Branch 0 taken 12 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 11 times.
✓ Branch 3 taken 1 times.
✓ Branch 5 taken 12 times.
✗ Branch 6 not taken.
12 setCandidate(xs_try_, us_try_, (was_feasible_) || (steplength_ == 1));
90 12 cost_ = cost_try_;
91 12 recalcDiff = true;
92 12 break;
93 }
94 }
95 }
96
97
2/2
✓ Branch 0 taken 48 times.
✓ Branch 1 taken 2 times.
50 if (steplength_ > th_stepdec_) {
98 48 decreaseRegularization();
99 }
100
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 50 times.
50 if (steplength_ <= th_stepinc_) {
101 increaseRegularization();
102 if (preg_ == reg_max_) {
103 STOP_PROFILER("SolverFDDP::solve");
104 return false;
105 }
106 }
107 50 stoppingCriteria();
108
109 50 const std::size_t n_callbacks = callbacks_.size();
110
2/2
✓ Branch 0 taken 22 times.
✓ Branch 1 taken 50 times.
72 for (std::size_t c = 0; c < n_callbacks; ++c) {
111 22 CallbackAbstract& callback = *callbacks_[c];
112 22 callback(*this);
113 }
114
115
4/4
✓ Branch 0 taken 33 times.
✓ Branch 1 taken 17 times.
✓ Branch 2 taken 10 times.
✓ Branch 3 taken 23 times.
50 if (was_feasible_ && stop_ < th_stop_) {
116
3/16
✗ Branch 2 not taken.
✓ Branch 3 taken 10 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✓ Branch 15 taken 10 times.
✗ Branch 17 not taken.
✓ Branch 18 taken 10 times.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
10 STOP_PROFILER("SolverFDDP::solve");
117 10 return true;
118 }
119 }
120
3/16
✗ Branch 2 not taken.
✓ Branch 3 taken 6 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✓ Branch 15 taken 6 times.
✗ Branch 17 not taken.
✓ Branch 18 taken 6 times.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
6 STOP_PROFILER("SolverFDDP::solve");
121 6 return false;
122 }
123
124 54 const Eigen::Vector2d& SolverFDDP::expectedImprovement() {
125 54 dv_ = 0;
126 54 const std::size_t T = this->problem_->get_T();
127
2/2
✓ Branch 0 taken 19 times.
✓ Branch 1 taken 35 times.
54 if (!is_feasible_) {
128 // NB: The dimension of vectors xs_try_ and xs_ are T+1, whereas the
129 // dimension of dx_ is T. Here, we are re-using the final element of dx_ for
130 // the computation of the difference at the terminal node. Using the access
131 // iterator back() this re-use of the final element is fine. Cf. the
132 // discussion at https://github.com/loco-3d/crocoddyl/issues/1022
133
3/6
✓ Branch 8 taken 19 times.
✗ Branch 9 not taken.
✓ Branch 12 taken 19 times.
✗ Branch 13 not taken.
✓ Branch 15 taken 19 times.
✗ Branch 16 not taken.
38 problem_->get_terminalModel()->get_state()->diff(xs_try_.back(), xs_.back(),
134 19 dx_.back());
135
2/4
✓ Branch 4 taken 19 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 19 times.
✗ Branch 8 not taken.
19 fTVxx_p_.noalias() = Vxx_.back() * dx_.back();
136 19 dv_ -= fs_.back().dot(fTVxx_p_);
137 const std::vector<std::shared_ptr<ActionModelAbstract> >& models =
138 19 problem_->get_runningModels();
139
140
2/2
✓ Branch 0 taken 197 times.
✓ Branch 1 taken 19 times.
216 for (std::size_t t = 0; t < T; ++t) {
141
3/6
✓ Branch 8 taken 197 times.
✗ Branch 9 not taken.
✓ Branch 12 taken 197 times.
✗ Branch 13 not taken.
✓ Branch 15 taken 197 times.
✗ Branch 16 not taken.
197 models[t]->get_state()->diff(xs_try_[t], xs_[t], dx_[t]);
142
2/4
✓ Branch 4 taken 197 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 197 times.
✗ Branch 8 not taken.
197 fTVxx_p_.noalias() = Vxx_[t] * dx_[t];
143 197 dv_ -= fs_[t].dot(fTVxx_p_);
144 }
145 }
146 54 d_[0] = dg_ + dv_;
147 54 d_[1] = dq_ - 2 * dv_;
148 54 return d_;
149 }
150
151 50 void SolverFDDP::updateExpectedImprovement() {
152 50 dg_ = 0;
153 50 dq_ = 0;
154 50 const std::size_t T = this->problem_->get_T();
155
2/2
✓ Branch 0 taken 17 times.
✓ Branch 1 taken 33 times.
50 if (!is_feasible_) {
156 17 dg_ -= Vx_.back().dot(fs_.back());
157
2/4
✓ Branch 4 taken 17 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 17 times.
✗ Branch 8 not taken.
17 fTVxx_p_.noalias() = Vxx_.back() * fs_.back();
158 17 dq_ += fs_.back().dot(fTVxx_p_);
159 }
160 const std::vector<std::shared_ptr<ActionModelAbstract> >& models =
161 50 problem_->get_runningModels();
162
2/2
✓ Branch 0 taken 564 times.
✓ Branch 1 taken 50 times.
614 for (std::size_t t = 0; t < T; ++t) {
163 564 const std::size_t nu = models[t]->get_nu();
164
1/2
✓ Branch 0 taken 564 times.
✗ Branch 1 not taken.
564 if (nu != 0) {
165 564 dg_ += Qu_[t].dot(k_[t]);
166 564 dq_ -= k_[t].dot(Quuk_[t]);
167 }
168
2/2
✓ Branch 0 taken 175 times.
✓ Branch 1 taken 389 times.
564 if (!is_feasible_) {
169 175 dg_ -= Vx_[t].dot(fs_[t]);
170
2/4
✓ Branch 4 taken 175 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 175 times.
✗ Branch 8 not taken.
175 fTVxx_p_.noalias() = Vxx_[t] * fs_[t];
171 175 dq_ += fs_[t].dot(fTVxx_p_);
172 }
173 }
174 50 }
175
176 45 void SolverFDDP::forwardPass(const double steplength) {
177
2/4
✓ Branch 0 taken 45 times.
✗ Branch 1 not taken.
✗ Branch 2 not taken.
✓ Branch 3 taken 45 times.
45 if (steplength > 1. || steplength < 0.) {
178 throw_pretty("Invalid argument: "
179 << "invalid step length, value is between 0. to 1.");
180 }
181
3/16
✗ Branch 2 not taken.
✓ Branch 3 taken 45 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✓ Branch 15 taken 45 times.
✗ Branch 17 not taken.
✓ Branch 18 taken 45 times.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
45 START_PROFILER("SolverFDDP::forwardPass");
182 45 cost_try_ = 0.;
183 45 xnext_ = problem_->get_x0();
184 45 const std::size_t T = problem_->get_T();
185 const std::vector<std::shared_ptr<ActionModelAbstract> >& models =
186 45 problem_->get_runningModels();
187 const std::vector<std::shared_ptr<ActionDataAbstract> >& datas =
188 45 problem_->get_runningDatas();
189
4/4
✓ Branch 0 taken 18 times.
✓ Branch 1 taken 27 times.
✓ Branch 2 taken 14 times.
✓ Branch 3 taken 4 times.
45 if ((is_feasible_) || (steplength == 1)) {
190
2/2
✓ Branch 0 taken 475 times.
✓ Branch 1 taken 41 times.
516 for (std::size_t t = 0; t < T; ++t) {
191 475 const std::shared_ptr<ActionModelAbstract>& m = models[t];
192 475 const std::shared_ptr<ActionDataAbstract>& d = datas[t];
193 475 const std::size_t nu = m->get_nu();
194
195 475 xs_try_[t] = xnext_;
196
3/6
✓ Branch 7 taken 475 times.
✗ Branch 8 not taken.
✓ Branch 11 taken 475 times.
✗ Branch 12 not taken.
✓ Branch 14 taken 475 times.
✗ Branch 15 not taken.
475 m->get_state()->diff(xs_[t], xs_try_[t], dx_[t]);
197
1/2
✓ Branch 0 taken 475 times.
✗ Branch 1 not taken.
475 if (nu != 0) {
198
5/10
✓ Branch 5 taken 475 times.
✗ Branch 6 not taken.
✓ Branch 9 taken 475 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 475 times.
✗ Branch 13 not taken.
✓ Branch 16 taken 475 times.
✗ Branch 17 not taken.
✓ Branch 19 taken 475 times.
✗ Branch 20 not taken.
475 us_try_[t].noalias() = us_[t] - k_[t] * steplength - K_[t] * dx_[t];
199
2/4
✓ Branch 5 taken 475 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 475 times.
✗ Branch 9 not taken.
475 m->calc(d, xs_try_[t], us_try_[t]);
200 } else {
201 m->calc(d, xs_try_[t]);
202 }
203 475 xnext_ = d->xnext;
204 475 cost_try_ += d->cost;
205
206
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 475 times.
475 if (raiseIfNaN(cost_try_)) {
207 STOP_PROFILER("SolverFDDP::forwardPass");
208 throw_pretty("forward_error");
209 }
210
1/2
✗ Branch 2 not taken.
✓ Branch 3 taken 475 times.
475 if (raiseIfNaN(xnext_.lpNorm<Eigen::Infinity>())) {
211 STOP_PROFILER("SolverFDDP::forwardPass");
212 throw_pretty("forward_error");
213 }
214 }
215
216 const std::shared_ptr<ActionModelAbstract>& m =
217 41 problem_->get_terminalModel();
218 41 const std::shared_ptr<ActionDataAbstract>& d = problem_->get_terminalData();
219 41 xs_try_.back() = xnext_;
220
1/2
✓ Branch 4 taken 41 times.
✗ Branch 5 not taken.
41 m->calc(d, xs_try_.back());
221 41 cost_try_ += d->cost;
222
223
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 41 times.
41 if (raiseIfNaN(cost_try_)) {
224 STOP_PROFILER("SolverFDDP::forwardPass");
225 throw_pretty("forward_error");
226 }
227 41 } else {
228
2/2
✓ Branch 0 taken 43 times.
✓ Branch 1 taken 4 times.
47 for (std::size_t t = 0; t < T; ++t) {
229 43 const std::shared_ptr<ActionModelAbstract>& m = models[t];
230 43 const std::shared_ptr<ActionDataAbstract>& d = datas[t];
231 43 const std::size_t nu = m->get_nu();
232
4/8
✓ Branch 7 taken 43 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 43 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 43 times.
✗ Branch 14 not taken.
✓ Branch 16 taken 43 times.
✗ Branch 17 not taken.
43 m->get_state()->integrate(xnext_, fs_[t] * (steplength - 1), xs_try_[t]);
233
3/6
✓ Branch 7 taken 43 times.
✗ Branch 8 not taken.
✓ Branch 11 taken 43 times.
✗ Branch 12 not taken.
✓ Branch 14 taken 43 times.
✗ Branch 15 not taken.
43 m->get_state()->diff(xs_[t], xs_try_[t], dx_[t]);
234
1/2
✓ Branch 0 taken 43 times.
✗ Branch 1 not taken.
43 if (nu != 0) {
235
5/10
✓ Branch 5 taken 43 times.
✗ Branch 6 not taken.
✓ Branch 9 taken 43 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 43 times.
✗ Branch 13 not taken.
✓ Branch 16 taken 43 times.
✗ Branch 17 not taken.
✓ Branch 19 taken 43 times.
✗ Branch 20 not taken.
43 us_try_[t].noalias() = us_[t] - k_[t] * steplength - K_[t] * dx_[t];
236
2/4
✓ Branch 5 taken 43 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 43 times.
✗ Branch 9 not taken.
43 m->calc(d, xs_try_[t], us_try_[t]);
237 } else {
238 m->calc(d, xs_try_[t]);
239 }
240 43 xnext_ = d->xnext;
241 43 cost_try_ += d->cost;
242
243
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 43 times.
43 if (raiseIfNaN(cost_try_)) {
244 STOP_PROFILER("SolverFDDP::forwardPass");
245 throw_pretty("forward_error");
246 }
247
1/2
✗ Branch 2 not taken.
✓ Branch 3 taken 43 times.
43 if (raiseIfNaN(xnext_.lpNorm<Eigen::Infinity>())) {
248 STOP_PROFILER("SolverFDDP::forwardPass");
249 throw_pretty("forward_error");
250 }
251 }
252
253 const std::shared_ptr<ActionModelAbstract>& m =
254 4 problem_->get_terminalModel();
255 4 const std::shared_ptr<ActionDataAbstract>& d = problem_->get_terminalData();
256
4/8
✓ Branch 6 taken 4 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 4 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 4 times.
✗ Branch 13 not taken.
✓ Branch 15 taken 4 times.
✗ Branch 16 not taken.
8 m->get_state()->integrate(xnext_, fs_.back() * (steplength - 1),
257 4 xs_try_.back());
258
1/2
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
4 m->calc(d, xs_try_.back());
259 4 cost_try_ += d->cost;
260
261
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 4 times.
4 if (raiseIfNaN(cost_try_)) {
262 STOP_PROFILER("SolverFDDP::forwardPass");
263 throw_pretty("forward_error");
264 }
265 }
266
3/16
✗ Branch 2 not taken.
✓ Branch 3 taken 45 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
✗ Branch 14 not taken.
✓ Branch 15 taken 45 times.
✗ Branch 17 not taken.
✓ Branch 18 taken 45 times.
✗ Branch 20 not taken.
✗ Branch 21 not taken.
✗ Branch 23 not taken.
✗ Branch 24 not taken.
45 STOP_PROFILER("SolverFDDP::forwardPass");
267 45 }
268
269 double SolverFDDP::get_th_acceptnegstep() const { return th_acceptnegstep_; }
270
271 void SolverFDDP::set_th_acceptnegstep(const double th_acceptnegstep) {
272 if (0. > th_acceptnegstep) {
273 throw_pretty(
274 "Invalid argument: " << "th_acceptnegstep value has to be positive.");
275 }
276 th_acceptnegstep_ = th_acceptnegstep;
277 }
278
279 } // namespace crocoddyl
280