src/modules/robot/Planner.cpp

   1 /*
   2       This file is part of Smoothie (http://smoothieware.org/). The motion control part is heavily based on Grbl (https://github.com/simen/grbl) with additions from Sungeun K. Jeon (https://github.com/chamnit/grbl)
   3       Smoothie is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
   4       Smoothie is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
   5       You should have received a copy of the GNU General Public License along with Smoothie. If not, see <http://www.gnu.org/licenses/>.
   6 */
   7
   8 using namespace std;
   9 #include <vector>
  10
  11 #include "mri.h"
  12 #include "nuts_bolts.h"
  13 #include "RingBuffer.h"
  14 #include "Gcode.h"
  15 #include "Module.h"
  16 #include "Kernel.h"
  17 #include "Block.h"
  18 #include "Planner.h"
  19 #include "Conveyor.h"
  20 #include "StepperMotor.h"
  21 #include "Config.h"
  22 #include "checksumm.h"
  23 #include "Robot.h"
  24 #include "ConfigValue.h"
  25
  26 #include <math.h>
  27 #include <algorithm>
  28
  29 #define junction_deviation_checksum    CHECKSUM("junction_deviation")
  30 #define z_junction_deviation_checksum  CHECKSUM("z_junction_deviation")
  31 #define minimum_planner_speed_checksum CHECKSUM("minimum_planner_speed")
  32
  33 // The Planner does the acceleration math for the queue of Blocks ( movements ).
  34 // It makes sure the speed stays within the configured constraints ( acceleration, junction_deviation, etc )
  35 // It goes over the list in both direction, every time a block is added, re-doing the math to make sure everything is optimal
  36
  37 Planner::Planner()
  38 {
  39     memset(this->previous_unit_vec, 0, sizeof this->previous_unit_vec);
  40     config_load();
  41 }
  42
  43 // Configure acceleration
  44 void Planner::config_load()
  45 {
  46     this->junction_deviation = THEKERNEL->config->value(junction_deviation_checksum)->by_default(0.05F)->as_number();
  47     this->z_junction_deviation = THEKERNEL->config->value(z_junction_deviation_checksum)->by_default(NAN)->as_number(); // disabled by default
  48     this->minimum_planner_speed = THEKERNEL->config->value(minimum_planner_speed_checksum)->by_default(0.0f)->as_number();
  49 }
  50
  51
  52 // Append a block to the queue, compute it's speed factors
  53 bool Planner::append_block( ActuatorCoordinates &actuator_pos, uint8_t n_motors, float rate_mm_s, float distance, float *unit_vec, float acceleration)
  54 {
  55     // Create ( recycle ) a new block
  56     Block* block = THECONVEYOR->queue.head_ref();
  57
  58     // Direction bits
  59     bool has_steps= false;
  60     for (size_t i = 0; i < n_motors; i++) {
  61         int32_t steps = THEROBOT->actuators[i]->steps_to_target(actuator_pos[i]);
  62         // Update current position
  63         if(steps != 0) {
  64             THEROBOT->actuators[i]->update_last_milestones(actuator_pos[i], steps);
  65             has_steps= true;
  66         }
  67
  68         // find direction
  69         block->direction_bits[i] = (steps < 0) ? 1 : 0;
  70         // save actual steps in block
  71         block->steps[i] = labs(steps);
  72     }
  73
  74     // sometimres even though there is a detectable movement it turns out there are no steps to be had from such a small move
  75     if(!has_steps) return false;
  76
  77     // use default JD
  78     float junction_deviation = this->junction_deviation;
  79
  80     // use either regular junction deviation or z specific and see if a primary axis move
  81     block->primary_axis= true;
  82     if(block->steps[ALPHA_STEPPER] == 0 && block->steps[BETA_STEPPER] == 0){
  83         if(block->steps[GAMMA_STEPPER] != 0) {
  84             // z only move
  85             if(!isnan(this->z_junction_deviation)) junction_deviation = this->z_junction_deviation;
  86         }else{
  87             // is not a primary axis move
  88             block->primary_axis= false;
  89         }
  90     }
  91
  92     block->acceleration = acceleration; // save in block
  93
  94     // Max number of steps, for all axes
  95     auto mi= std::max_element(block->steps.begin(), block->steps.end());
  96     block->steps_event_count = *mi;
  97
  98     block->millimeters = distance;
  99
 100     // Calculate speed in mm/sec for each axis. No divide by zero due to previous checks.
 101     if( distance > 0.0F ) {
 102         block->nominal_speed = rate_mm_s;           // (mm/s) Always > 0
 103         block->nominal_rate = block->steps_event_count * rate_mm_s / distance; // (step/s) Always > 0
 104     } else {
 105         block->nominal_speed = 0.0F;
 106         block->nominal_rate  = 0;
 107     }
 108
 109     // Compute the acceleration rate for the trapezoid generator. Depending on the slope of the line
 110     // average travel per step event changes. For a line along one axis the travel per step event
 111     // is equal to the travel/step in the particular axis. For a 45 degree line the steppers of both
 112     // axes might step for every step event. Travel per step event is then sqrt(travel_x^2+travel_y^2).
 113
 114     // Compute maximum allowable entry speed at junction by centripetal acceleration approximation.
 115     // Let a circle be tangent to both previous and current path line segments, where the junction
 116     // deviation is defined as the distance from the junction to the closest edge of the circle,
 117     // colinear with the circle center. The circular segment joining the two paths represents the
 118     // path of centripetal acceleration. Solve for max velocity based on max acceleration about the
 119     // radius of the circle, defined indirectly by junction deviation. This may be also viewed as
 120     // path width or max_jerk in the previous grbl version. This approach does not actually deviate
 121     // from path, but used as a robust way to compute cornering speeds, as it takes into account the
 122     // nonlinearities of both the junction angle and junction velocity.
 123
 124     // NOTE however it does not take into account independent axis, in most cartesian X and Y and Z are totally independent
 125     // and this allows one to stop with little to no decleration in many cases. This is particualrly bad on leadscrew based systems that will skip steps.
 126     float vmax_junction = minimum_planner_speed; // Set default max junction speed
 127
 128     // if unit_vec was null then it was not a primary axis move so we skip the junction deviation stuff
 129     if (unit_vec != nullptr && !THECONVEYOR->is_queue_empty()) {
 130         Block *prev_block= THECONVEYOR->queue.item_ref(THECONVEYOR->queue.prev(THECONVEYOR->queue.head_i));
 131         float previous_nominal_speed = prev_block->primary_axis ? prev_block->nominal_speed : 0;
 132
 133         if (junction_deviation > 0.0F && previous_nominal_speed > 0.0F) {
 134             // Compute cosine of angle between previous and current path. (prev_unit_vec is negative)
 135             // NOTE: Max junction velocity is computed without sin() or acos() by trig half angle identity.
 136             float cos_theta = - this->previous_unit_vec[X_AXIS] * unit_vec[X_AXIS]
 137                               - this->previous_unit_vec[Y_AXIS] * unit_vec[Y_AXIS]
 138                               - this->previous_unit_vec[Z_AXIS] * unit_vec[Z_AXIS] ;
 139
 140             // Skip and use default max junction speed for 0 degree acute junction.
 141             if (cos_theta < 0.95F) {
 142                 vmax_junction = std::min(previous_nominal_speed, block->nominal_speed);
 143                 // Skip and avoid divide by zero for straight junctions at 180 degrees. Limit to min() of nominal speeds.
 144                 if (cos_theta > -0.95F) {
 145                     // Compute maximum junction velocity based on maximum acceleration and junction deviation
 146                     float sin_theta_d2 = sqrtf(0.5F * (1.0F - cos_theta)); // Trig half angle identity. Always positive.
 147                     vmax_junction = std::min(vmax_junction, sqrtf(acceleration * junction_deviation * sin_theta_d2 / (1.0F - sin_theta_d2)));
 148                 }
 149             }
 150         }
 151     }
 152     block->max_entry_speed = vmax_junction;
 153
 154     // Initialize block entry speed. Compute based on deceleration to user-defined minimum_planner_speed.
 155     float v_allowable = max_allowable_speed(-acceleration, minimum_planner_speed, block->millimeters);
 156     block->entry_speed = std::min(vmax_junction, v_allowable);
 157
 158     // Initialize planner efficiency flags
 159     // Set flag if block will always reach maximum junction speed regardless of entry/exit speeds.
 160     // If a block can de/ac-celerate from nominal speed to zero within the length of the block, then
 161     // the current block and next block junction speeds are guaranteed to always be at their maximum
 162     // junction speeds in deceleration and acceleration, respectively. This is due to how the current
 163     // block nominal speed limits both the current and next maximum junction speeds. Hence, in both
 164     // the reverse and forward planners, the corresponding block junction speed will always be at the
 165     // the maximum junction speed and may always be ignored for any speed reduction checks.
 166     if (block->nominal_speed <= v_allowable) { block->nominal_length_flag = true; }
 167     else { block->nominal_length_flag = false; }
 168
 169     // Always calculate trapezoid for new block
 170     block->recalculate_flag = true;
 171
 172     // Update previous path unit_vector and nominal speed
 173     if(unit_vec != nullptr) {
 174         memcpy(previous_unit_vec, unit_vec, sizeof(previous_unit_vec)); // previous_unit_vec[] = unit_vec[]
 175     }else{
 176         memset(previous_unit_vec, 0, sizeof(previous_unit_vec));
 177     }
 178
 179     // Math-heavy re-computing of the whole queue to take the new
 180     this->recalculate();
 181
 182     // The block can now be used
 183     block->ready();
 184
 185     THECONVEYOR->queue_head_block();
 186
 187     return true;
 188 }
 189
 190 void Planner::recalculate()
 191 {
 192     Conveyor::Queue_t &queue = THECONVEYOR->queue;
 193
 194     unsigned int block_index;
 195
 196     Block* previous;
 197     Block* current;
 198
 199     /*
 200      * a newly added block is decel limited
 201      *
 202      * we find its max entry speed given its exit speed
 203      *
 204      * for each block, walking backwards in the queue:
 205      *
 206      * if max entry speed == current entry speed
 207      * then we can set recalculate to false, since clearly adding another block didn't allow us to enter faster
 208      * and thus we don't need to check entry speed for this block any more
 209      *
 210      * once we find an accel limited block, we must find the max exit speed and walk the queue forwards
 211      *
 212      * for each block, walking forwards in the queue:
 213      *
 214      * given the exit speed of the previous block and our own max entry speed
 215      * we can tell if we're accel or decel limited (or coasting)
 216      *
 217      * if prev_exit > max_entry
 218      *     then we're still decel limited. update previous trapezoid with our max entry for prev exit
 219      * if max_entry >= prev_exit
 220      *     then we're accel limited. set recalculate to false, work out max exit speed
 221      *
 222      * finally, work out trapezoid for the final (and newest) block.
 223      */
 224
 225     /*
 226      * Step 1:
 227      * For each block, given the exit speed and acceleration, find the maximum entry speed
 228      */
 229
 230     float entry_speed = minimum_planner_speed;
 231
 232     block_index = queue.head_i;
 233     current     = queue.item_ref(block_index);
 234
 235     if (!queue.is_empty()) {
 236         while ((block_index != queue.tail_i) && current->recalculate_flag) {
 237             entry_speed = current->reverse_pass(entry_speed);
 238
 239             block_index = queue.prev(block_index);
 240             current     = queue.item_ref(block_index);
 241         }
 242
 243         /*
 244          * Step 2:
 245          * now current points to either tail or first non-recalculate block
 246          * and has not had its reverse_pass called
 247          * or its calculate_trapezoid
 248          * entry_speed is set to the *exit* speed of current.
 249          * each block from current to head has its entry speed set to its max entry speed- limited by decel or nominal_rate
 250          */
 251
 252         float exit_speed = current->max_exit_speed();
 253
 254         while (block_index != queue.head_i) {
 255             previous    = current;
 256             block_index = queue.next(block_index);
 257             current     = queue.item_ref(block_index);
 258
 259             // we pass the exit speed of the previous block
 260             // so this block can decide if it's accel or decel limited and update its fields as appropriate
 261             exit_speed = current->forward_pass(exit_speed);
 262
 263             previous->calculate_trapezoid(previous->entry_speed, current->entry_speed);
 264         }
 265     }
 266
 267     /*
 268      * Step 3:
 269      * work out trapezoid for final (and newest) block
 270      */
 271
 272     // now current points to the head item
 273     // which has not had calculate_trapezoid run yet
 274     current->calculate_trapezoid(current->entry_speed, minimum_planner_speed);
 275 }
 276
 277
 278 // Calculates the maximum allowable speed at this point when you must be able to reach target_velocity using the
 279 // acceleration within the allotted distance.
 280 float Planner::max_allowable_speed(float acceleration, float target_velocity, float distance)
 281 {
 282     // Was acceleration*60*60*distance, in case this breaks, but here we prefer to use seconds instead of minutes
 283     return(sqrtf(target_velocity * target_velocity - 2.0F * acceleration * distance));
 284 }
 285
 286