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
  21 #define acceleration_checksum          CHECKSUM("acceleration")
  22 #define max_jerk_checksum              CHECKSUM("max_jerk")
  23 #define junction_deviation_checksum    CHECKSUM("junction_deviation")
  24 #define minimum_planner_speed_checksum CHECKSUM("minimum_planner_speed")
  25
  26 // The Planner does the acceleration math for the queue of Blocks ( movements ).
  27 // It makes sure the speed stays within the configured constraints ( acceleration, junction_deviation, etc )
  28 // It goes over the list in both direction, every time a block is added, re-doing the math to make sure everything is optimal
  29
  30 Planner::Planner(){
  31     clear_vector_float(this->previous_unit_vec);
  32     this->has_deleted_block = false;
  33 }
  34
  35 void Planner::on_module_loaded(){
  36     register_for_event(ON_CONFIG_RELOAD);
  37     this->on_config_reload(this);
  38 }
  39
  40 // Configure acceleration
  41 void Planner::on_config_reload(void* argument){
  42     this->acceleration =       THEKERNEL->config->value(acceleration_checksum       )->by_default(100.0F )->as_number(); // Acceleration is in mm/s^2, see https://github.com/grbl/grbl/commit/9141ad282540eaa50a41283685f901f29c24ddbd#planner.c
  43     this->junction_deviation = THEKERNEL->config->value(junction_deviation_checksum )->by_default(  0.05F)->as_number();
  44     this->minimum_planner_speed = THEKERNEL->config->value(minimum_planner_speed_checksum )->by_default(0.0f)->as_number();
  45 }
  46
  47
  48 // Append a block to the queue, compute it's speed factors
  49 void Planner::append_block( float actuator_pos[], float rate_mm_s, float distance, float unit_vec[] )
  50 {
  51     // Create ( recycle ) a new block
  52     Block* block = THEKERNEL->conveyor->queue.head_ref();
  53
  54     // Direction bits
  55     block->direction_bits = 0;
  56     for (int i = 0; i < 3; i++)
  57     {
  58         int steps = THEKERNEL->robot->actuators[i]->steps_to_target(actuator_pos[i]);
  59
  60         if (steps < 0)
  61             block->direction_bits |= (1<<i);
  62
  63         // Update current position
  64         THEKERNEL->robot->actuators[i]->last_milestone_steps += steps;
  65         THEKERNEL->robot->actuators[i]->last_milestone_mm = actuator_pos[i];
  66
  67         block->steps[i] = labs(steps);
  68     }
  69
  70     // Max number of steps, for all axes
  71     block->steps_event_count = max( block->steps[ALPHA_STEPPER], max( block->steps[BETA_STEPPER], block->steps[GAMMA_STEPPER] ) );
  72
  73     block->millimeters = distance;
  74
  75     // Calculate speed in mm/minute for each axis. No divide by zero due to previous checks.
  76     // NOTE: Minimum stepper speed is limited by MINIMUM_STEPS_PER_MINUTE in stepper.c
  77     if( distance > 0.0F ){
  78         block->nominal_speed = rate_mm_s;           // (mm/s) Always > 0
  79         block->nominal_rate = ceil(block->steps_event_count * rate_mm_s / distance); // (step/s) Always > 0
  80     }else{
  81         block->nominal_speed = 0.0F;
  82         block->nominal_rate  = 0;
  83     }
  84
  85     // Compute the acceleration rate for the trapezoid generator. Depending on the slope of the line
  86     // average travel per step event changes. For a line along one axis the travel per step event
  87     // is equal to the travel/step in the particular axis. For a 45 degree line the steppers of both
  88     // axes might step for every step event. Travel per step event is then sqrt(travel_x^2+travel_y^2).
  89     // To generate trapezoids with contant acceleration between blocks the rate_delta must be computed
  90     // specifically for each line to compensate for this phenomenon:
  91     // Convert universal acceleration for direction-dependent stepper rate change parameter
  92     block->rate_delta = (block->steps_event_count * acceleration) / (distance * THEKERNEL->stepper->acceleration_ticks_per_second); // (step/min/acceleration_tick)
  93
  94     // Compute maximum allowable entry speed at junction by centripetal acceleration approximation.
  95     // Let a circle be tangent to both previous and current path line segments, where the junction
  96     // deviation is defined as the distance from the junction to the closest edge of the circle,
  97     // colinear with the circle center. The circular segment joining the two paths represents the
  98     // path of centripetal acceleration. Solve for max velocity based on max acceleration about the
  99     // radius of the circle, defined indirectly by junction deviation. This may be also viewed as
 100     // path width or max_jerk in the previous grbl version. This approach does not actually deviate
 101     // from path, but used as a robust way to compute cornering speeds, as it takes into account the
 102     // nonlinearities of both the junction angle and junction velocity.
 103     float vmax_junction = minimum_planner_speed; // Set default max junction speed
 104
 105     if (!THEKERNEL->conveyor->queue.is_empty())
 106     {
 107         float previous_nominal_speed = THEKERNEL->conveyor->queue.item_ref(THEKERNEL->conveyor->queue.prev(THEKERNEL->conveyor->queue.head_i))->nominal_speed;
 108
 109         if (previous_nominal_speed > 0.0F) {
 110             // Compute cosine of angle between previous and current path. (prev_unit_vec is negative)
 111             // NOTE: Max junction velocity is computed without sin() or acos() by trig half angle identity.
 112             float cos_theta = - this->previous_unit_vec[X_AXIS] * unit_vec[X_AXIS]
 113                                 - this->previous_unit_vec[Y_AXIS] * unit_vec[Y_AXIS]
 114                                 - this->previous_unit_vec[Z_AXIS] * unit_vec[Z_AXIS] ;
 115
 116             // Skip and use default max junction speed for 0 degree acute junction.
 117             if (cos_theta < 0.95F) {
 118                 vmax_junction = min(previous_nominal_speed, block->nominal_speed);
 119                 // Skip and avoid divide by zero for straight junctions at 180 degrees. Limit to min() of nominal speeds.
 120                 if (cos_theta > -0.95F) {
 121                     // Compute maximum junction velocity based on maximum acceleration and junction deviation
 122                     float sin_theta_d2 = sqrtf(0.5F * (1.0F - cos_theta)); // Trig half angle identity. Always positive.
 123                     vmax_junction = min(vmax_junction, sqrtf(this->acceleration * this->junction_deviation * sin_theta_d2 / (1.0F - sin_theta_d2)));
 124                 }
 125             }
 126         }
 127     }
 128     block->max_entry_speed = vmax_junction;
 129
 130     // Initialize block entry speed. Compute based on deceleration to user-defined minimum_planner_speed.
 131     float v_allowable = max_allowable_speed(-acceleration, minimum_planner_speed, block->millimeters); //TODO: Get from config
 132     block->entry_speed = min(vmax_junction, v_allowable);
 133
 134     // Initialize planner efficiency flags
 135     // Set flag if block will always reach maximum junction speed regardless of entry/exit speeds.
 136     // If a block can de/ac-celerate from nominal speed to zero within the length of the block, then
 137     // the current block and next block junction speeds are guaranteed to always be at their maximum
 138     // junction speeds in deceleration and acceleration, respectively. This is due to how the current
 139     // block nominal speed limits both the current and next maximum junction speeds. Hence, in both
 140     // the reverse and forward planners, the corresponding block junction speed will always be at the
 141     // the maximum junction speed and may always be ignored for any speed reduction checks.
 142     if (block->nominal_speed <= v_allowable) { block->nominal_length_flag = true; }
 143     else { block->nominal_length_flag = false; }
 144
 145     // Always calculate trapezoid for new block
 146     block->recalculate_flag = true;
 147
 148     // Update previous path unit_vector and nominal speed
 149     memcpy(this->previous_unit_vec, unit_vec, sizeof(previous_unit_vec)); // previous_unit_vec[] = unit_vec[]
 150
 151     // Math-heavy re-computing of the whole queue to take the new
 152     this->recalculate();
 153
 154     // The block can now be used
 155     block->ready();
 156
 157     THEKERNEL->conveyor->queue_head_block();
 158 }
 159
 160
 161 // Recalculates the motion plan according to the following algorithm:
 162 //
 163 // 1. Go over every block in reverse order and calculate a junction speed reduction (i.e. block_t.entry_factor)
 164 // so that:
 165 //   a. The junction jerk is within the set limit
 166 //   b. No speed reduction within one block requires faster deceleration than the one, true constant
 167 //      acceleration.
 168 // 2. Go over every block in chronological order and dial down junction speed reduction values if
 169 //   a. The speed increase within one block would require faster accelleration than the one, true
 170 //      constant acceleration.
 171 //
 172 // When these stages are complete all blocks have an entry_factor that will allow all speed changes to
 173 // be performed using only the one, true constant acceleration, and where no junction jerk is jerkier than
 174 // the set limit. Finally it will:
 175 //
 176 // 3. Recalculate trapezoids for all blocks.
 177 //
 178 void Planner::recalculate() {
 179     Conveyor::Queue_t &queue = THEKERNEL->conveyor->queue;
 180
 181     unsigned int block_index;
 182
 183     Block* previous;
 184     Block* current;
 185
 186     /*
 187      * a newly added block is decel limited
 188      *
 189      * we find its max entry speed given its exit speed
 190      *
 191      * for each block, walking backwards in the queue:
 192      *
 193      * if max entry speed == current entry speed
 194      * then we can set recalculate to false, since clearly adding another block didn't allow us to enter faster
 195      * and thus we don't need to check entry speed for this block any more
 196      *
 197      * once we find an accel limited block, we must find the max exit speed and walk the queue forwards
 198      *
 199      * for each block, walking forwards in the queue:
 200      *
 201      * given the exit speed of the previous block and our own max entry speed
 202      * we can tell if we're accel or decel limited (or coasting)
 203      *
 204      * if prev_exit > max_entry
 205      *     then we're still decel limited. update previous trapezoid with our max entry for prev exit
 206      * if max_entry >= prev_exit
 207      *     then we're accel limited. set recalculate to false, work out max exit speed
 208      *
 209      * finally, work out trapezoid for the final (and newest) block.
 210      */
 211
 212     /*
 213      * Step 1:
 214      * For each block, given the exit speed and acceleration, find the maximum entry speed
 215      */
 216
 217     float entry_speed = minimum_planner_speed;
 218
 219     block_index = queue.head_i;
 220     current     = queue.item_ref(block_index);
 221
 222     if (!queue.is_empty())
 223     {
 224         while ((block_index != queue.tail_i) && current->recalculate_flag)
 225         {
 226             entry_speed = current->reverse_pass(entry_speed);
 227
 228             block_index = queue.prev(block_index);
 229             current     = queue.item_ref(block_index);
 230         }
 231
 232         /*
 233          * Step 2:
 234          * now current points to either tail or first non-recalculate block
 235          * and has not had its reverse_pass called
 236          * or its calc trap
 237          * entry_speed is set to the *exit* speed of current.
 238          * each block from current to head has its entry speed set to its max entry speed- limited by decel or nominal_rate
 239          */
 240
 241         float exit_speed = current->max_exit_speed();
 242
 243         while (block_index != queue.head_i)
 244         {
 245             previous    = current;
 246             block_index = queue.next(block_index);
 247             current     = queue.item_ref(block_index);
 248
 249             // we pass the exit speed of the previous block
 250             // so this block can decide if it's accel or decel limited and update its fields as appropriate
 251             exit_speed = current->forward_pass(exit_speed);
 252
 253             previous->calculate_trapezoid(previous->entry_speed, current->entry_speed);
 254         }
 255     }
 256
 257     /*
 258      * Step 3:
 259      * work out trapezoid for final (and newest) block
 260      */
 261
 262     // now current points to the head item
 263     // which has not had calculate_trapezoid run yet
 264     current->calculate_trapezoid(current->entry_speed, minimum_planner_speed);
 265 }
 266
 267
 268 // Calculates the maximum allowable speed at this point when you must be able to reach target_velocity using the
 269 // acceleration within the allotted distance.
 270 float Planner::max_allowable_speed(float acceleration, float target_velocity, float distance) {
 271   return(
 272     sqrtf(target_velocity*target_velocity-2.0F*acceleration*distance)  //Was acceleration*60*60*distance, in case this breaks, but here we prefer to use seconds instead of minutes
 273   );
 274 }
 275
 276