| Line |
Branch |
Exec |
Source |
| 1 |
|
|
// |
| 2 |
|
|
// Copyright (c) 2019 CNRS |
| 3 |
|
|
// |
| 4 |
|
|
// Author: Florent Lamiraux |
| 5 |
|
|
// |
| 6 |
|
|
|
| 7 |
|
|
#include "path-optimization/reeds-shepp/piecewise-quadratic.hh" |
| 8 |
|
|
|
| 9 |
|
|
namespace hpp { |
| 10 |
|
|
namespace core { |
| 11 |
|
|
namespace pathOptimization { |
| 12 |
|
|
namespace reedsShepp { |
| 13 |
|
|
|
| 14 |
|
|
using hpp::core::interval_t; |
| 15 |
|
|
|
| 16 |
|
✗ |
PiecewiseQuadraticPtr_t PiecewiseQuadratic::create(const value_type& initVel) { |
| 17 |
|
✗ |
PiecewiseQuadratic* ptr(new PiecewiseQuadratic(initVel)); |
| 18 |
|
✗ |
PiecewiseQuadraticPtr_t shPtr(ptr); |
| 19 |
|
✗ |
ptr->init(shPtr); |
| 20 |
|
✗ |
return shPtr; |
| 21 |
|
|
} |
| 22 |
|
|
|
| 23 |
|
✗ |
PiecewiseQuadraticPtr_t PiecewiseQuadratic::createCopy( |
| 24 |
|
|
const PiecewiseQuadraticPtr_t& other) { |
| 25 |
|
✗ |
PiecewiseQuadratic* ptr(new PiecewiseQuadratic(*other)); |
| 26 |
|
✗ |
PiecewiseQuadraticPtr_t shPtr(ptr); |
| 27 |
|
✗ |
ptr->init(shPtr); |
| 28 |
|
✗ |
return shPtr; |
| 29 |
|
|
} |
| 30 |
|
|
|
| 31 |
|
✗ |
hpp::core::TimeParameterizationPtr_t PiecewiseQuadratic::copy() const { |
| 32 |
|
✗ |
return createCopy(weak_.lock()); |
| 33 |
|
|
} |
| 34 |
|
|
|
| 35 |
|
✗ |
void PiecewiseQuadratic::init(const PiecewiseQuadraticWkPtr_t& weak) { |
| 36 |
|
✗ |
weak_ = weak; |
| 37 |
|
|
} |
| 38 |
|
|
|
| 39 |
|
✗ |
interval_t PiecewiseQuadratic::definitionInterval() const { |
| 40 |
|
✗ |
return interval_t(0, times_.back()); |
| 41 |
|
|
} |
| 42 |
|
|
|
| 43 |
|
✗ |
size_type PiecewiseQuadratic::findInterval(value_type t) const { |
| 44 |
|
✗ |
assert(t > -sqrt(std::numeric_limits<value_type>::epsilon())); |
| 45 |
|
✗ |
assert(times_.size() >= 2); |
| 46 |
|
✗ |
if (t < 0) t = 0; |
| 47 |
|
✗ |
for (std::size_t i = 1; i < times_.size(); ++i) { |
| 48 |
|
✗ |
if (t <= times_[i]) return i - 1; |
| 49 |
|
|
} |
| 50 |
|
✗ |
return times_.size() - 1; |
| 51 |
|
|
} |
| 52 |
|
|
|
| 53 |
|
✗ |
value_type PiecewiseQuadratic::value(const value_type& t) const { |
| 54 |
|
✗ |
size_type index = findInterval(t); |
| 55 |
|
✗ |
std::size_t i((std::size_t)index); |
| 56 |
|
✗ |
value_type ti = times_[i]; |
| 57 |
|
✗ |
return a_[i] * (t - ti) * (t - ti) + b_[i] * (t - ti) + c_[i]; |
| 58 |
|
|
} |
| 59 |
|
✗ |
value_type PiecewiseQuadratic::derivative(const value_type& t, |
| 60 |
|
|
const size_type& order) const { |
| 61 |
|
✗ |
size_type index = findInterval(t); |
| 62 |
|
✗ |
if (index < 0) return 0; |
| 63 |
|
✗ |
if ((std::size_t)index >= times_.size()) return 0; |
| 64 |
|
✗ |
std::size_t i((std::size_t)index); |
| 65 |
|
✗ |
value_type ti = times_[i]; |
| 66 |
|
✗ |
if (order == 1) { |
| 67 |
|
✗ |
return 2 * a_[i] * (t - ti) + b_[i]; |
| 68 |
|
✗ |
} else if (order == 2) { |
| 69 |
|
✗ |
return 2 * a_[i]; |
| 70 |
|
|
} else { |
| 71 |
|
✗ |
return 0; |
| 72 |
|
|
} |
| 73 |
|
|
} |
| 74 |
|
✗ |
value_type PiecewiseQuadratic::derivativeBound(const value_type& low, |
| 75 |
|
|
const value_type& up) const { |
| 76 |
|
✗ |
return std::max(fabs(derivative(low, 1)), fabs(derivative(up, 1))); |
| 77 |
|
|
} |
| 78 |
|
|
|
| 79 |
|
✗ |
void PiecewiseQuadratic::addSegments(const value_type& distance, |
| 80 |
|
|
const value_type& accel, |
| 81 |
|
|
const value_type& decel, |
| 82 |
|
|
const value_type& maxVel, |
| 83 |
|
|
const value_type& targetVel) { |
| 84 |
|
✗ |
value_type endValue = 0, endVel = initVel_, a, b, c; |
| 85 |
|
|
// endVel is the velocity at the end of the previous segment, |
| 86 |
|
|
// therefore at the beginning of this one. |
| 87 |
|
✗ |
assert(maxVel >= targetVel); |
| 88 |
|
✗ |
assert(maxVel >= initVel_); |
| 89 |
|
✗ |
assert(accel > 0); |
| 90 |
|
✗ |
assert(decel > 0); |
| 91 |
|
✗ |
assert(distance > 0); |
| 92 |
|
✗ |
if (distance < 1e-8) return; |
| 93 |
|
|
// time for reaching maximal velocity |
| 94 |
|
✗ |
value_type tacc = (maxVel - initVel_) / accel; |
| 95 |
|
|
// time for reaching end velocity |
| 96 |
|
✗ |
value_type tdec = (maxVel - targetVel) / decel; |
| 97 |
|
|
// distance travelled during tacc and tdec |
| 98 |
|
✗ |
value_type dacc = .5 * tacc * (initVel_ + maxVel); |
| 99 |
|
✗ |
value_type ddec = .5 * tdec * (targetVel + maxVel); |
| 100 |
|
|
// Test whether there is a constant speed segment |
| 101 |
|
✗ |
if (dacc + ddec < distance) { |
| 102 |
|
|
// There is a constant speed segment between accel and decel |
| 103 |
|
✗ |
value_type remainingDist = distance - dacc + ddec; |
| 104 |
|
✗ |
value_type tint = remainingDist / maxVel; |
| 105 |
|
|
// Add 3 segment |
| 106 |
|
|
// Acceleration |
| 107 |
|
✗ |
a = .5 * accel; |
| 108 |
|
✗ |
a_.push_back(a); |
| 109 |
|
✗ |
b = initVel_; |
| 110 |
|
✗ |
b_.push_back(b); |
| 111 |
|
✗ |
c = endValue; |
| 112 |
|
✗ |
c_.push_back(c); |
| 113 |
|
✗ |
times_.push_back(times_.back() + tacc); |
| 114 |
|
✗ |
endValue = a * tacc * tacc + b * tacc + c; |
| 115 |
|
✗ |
endVel = 2 * a * tacc + b; |
| 116 |
|
|
// Constant speed |
| 117 |
|
✗ |
a = 0; |
| 118 |
|
✗ |
a_.push_back(a); |
| 119 |
|
✗ |
b = endVel; |
| 120 |
|
✗ |
b_.push_back(b); |
| 121 |
|
✗ |
c = endValue; |
| 122 |
|
✗ |
c_.push_back(c); |
| 123 |
|
✗ |
times_.push_back(times_.back() + tint); |
| 124 |
|
✗ |
endValue = a * tint * tint + b * tint + c; |
| 125 |
|
✗ |
endVel = 2 * a * tint + b; |
| 126 |
|
|
// Deceleration |
| 127 |
|
✗ |
a = -.5 * decel; |
| 128 |
|
✗ |
a_.push_back(a); |
| 129 |
|
✗ |
b = endVel; |
| 130 |
|
✗ |
b_.push_back(b); |
| 131 |
|
✗ |
c = endValue; |
| 132 |
|
✗ |
c_.push_back(c); |
| 133 |
|
✗ |
times_.push_back(times_.back() + tdec); |
| 134 |
|
✗ |
endValue = a * tdec * tdec + b * tdec + c; |
| 135 |
|
✗ |
endVel = 2 * a * tdec + b; |
| 136 |
|
✗ |
} else if (distance < |
| 137 |
|
✗ |
.5 * (endVel * endVel - targetVel * targetVel) / decel) { |
| 138 |
|
|
// Distance too small to stop |
| 139 |
|
✗ |
value_type decel2 = |
| 140 |
|
✗ |
.5 * (endVel * endVel - targetVel * targetVel) / distance; |
| 141 |
|
✗ |
tdec = (endVel - targetVel) / decel2; |
| 142 |
|
|
// Deceleration |
| 143 |
|
✗ |
a = -.5 * decel2; |
| 144 |
|
✗ |
a_.push_back(a); |
| 145 |
|
✗ |
b = endVel; |
| 146 |
|
✗ |
b_.push_back(b); |
| 147 |
|
✗ |
c = endValue; |
| 148 |
|
✗ |
c_.push_back(c); |
| 149 |
|
✗ |
endValue = a * tdec * tdec + b * tdec + c; |
| 150 |
|
✗ |
endVel = 2 * a * tdec + b; |
| 151 |
|
✗ |
times_.push_back(times_.back() + tdec); |
| 152 |
|
|
} else { |
| 153 |
|
|
// There is no constant speed segment between accel and decel |
| 154 |
|
✗ |
value_type vmax = sqrt((decel * accel) / (decel + accel) * |
| 155 |
|
✗ |
(2 * distance + endVel * endVel / accel + |
| 156 |
|
✗ |
targetVel * targetVel / decel)); |
| 157 |
|
✗ |
tacc = (vmax - endVel) / accel; |
| 158 |
|
✗ |
tdec = (vmax - targetVel) / decel; |
| 159 |
|
✗ |
assert(fabs(distance - .5 * (tacc * (endVel + vmax) + |
| 160 |
|
|
tdec * (vmax + targetVel))) < 1e-8); |
| 161 |
|
|
// add 2 segments |
| 162 |
|
|
// Acceleration |
| 163 |
|
✗ |
a = .5 * accel; |
| 164 |
|
✗ |
a_.push_back(a); |
| 165 |
|
✗ |
b = endVel; |
| 166 |
|
✗ |
b_.push_back(b); |
| 167 |
|
✗ |
c = endValue; |
| 168 |
|
✗ |
c_.push_back(c); |
| 169 |
|
✗ |
endValue = a * tacc * tacc + b * tacc + c; |
| 170 |
|
✗ |
endVel = 2 * a * tacc + b; |
| 171 |
|
✗ |
times_.push_back(times_.back() + tacc); |
| 172 |
|
|
// Deceleration |
| 173 |
|
✗ |
a = -.5 * decel; |
| 174 |
|
✗ |
a_.push_back(a); |
| 175 |
|
✗ |
b = endVel; |
| 176 |
|
✗ |
b_.push_back(b); |
| 177 |
|
✗ |
c = endValue; |
| 178 |
|
✗ |
c_.push_back(c); |
| 179 |
|
✗ |
endValue = a * tdec * tdec + b * tdec + c; |
| 180 |
|
✗ |
endVel = 2 * a * tdec + b; |
| 181 |
|
✗ |
times_.push_back(times_.back() + tdec); |
| 182 |
|
|
} |
| 183 |
|
|
} |
| 184 |
|
|
|
| 185 |
|
|
} // namespace reedsShepp |
| 186 |
|
|
} // namespace pathOptimization |
| 187 |
|
|
} // namespace core |
| 188 |
|
|
} // namespace hpp |
| 189 |
|
|
|