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 // The Planner does the acceleration math for the queue of Blocks ( movements ).
  22 // It makes sure the speed stays within the configured constraints ( acceleration, junction_deviation, etc )
  23 // It goes over the list in both direction, every time a block is added, re-doing the math to make sure everything is optimal
  24
  25 Planner::Planner(){
  26     clear_vector(this->position);
  27     clear_vector_double(this->previous_unit_vec);
  28     this->previous_nominal_speed = 0.0;
  29     this->has_deleted_block = false;
  30 }
  31
  32 void Planner::on_module_loaded(){
  33     register_for_event(ON_CONFIG_RELOAD);
  34     this->on_config_reload(this);
  35 }
  36
  37 // Configure acceleration
  38 void Planner::on_config_reload(void* argument){
  39     this->acceleration =       THEKERNEL->config->value(acceleration_checksum       )->by_default(100 )->as_number() * 60 * 60; // Acceleration is in mm/minute^2, see https://github.com/grbl/grbl/commit/9141ad282540eaa50a41283685f901f29c24ddbd#planner.c
  40     this->junction_deviation = THEKERNEL->config->value(junction_deviation_checksum )->by_default(0.05)->as_number();
  41 }
  42
  43
  44 // Append a block to the queue, compute it's speed factors
  45 void Planner::append_block( int target[], double feed_rate, double distance, double deltas[] ){
  46
  47     // Stall here if the queue is ful
  48     THEKERNEL->conveyor->wait_for_queue(2);
  49
  50     // Create ( recycle ) a new block
  51     Block* block = THEKERNEL->conveyor->new_block();
  52     block->planner = this;
  53
  54     // Direction bits
  55     block->direction_bits = 0;
  56     for( int stepper=ALPHA_STEPPER; stepper<=GAMMA_STEPPER; stepper++){
  57         if( target[stepper] < position[stepper] ){ block->direction_bits |= (1<<stepper); }
  58     }
  59
  60     // Number of steps for each stepper
  61     for( int stepper=ALPHA_STEPPER; stepper<=GAMMA_STEPPER; stepper++){ block->steps[stepper] = labs(target[stepper] - this->position[stepper]); }
  62
  63     // Max number of steps, for all axes
  64     block->steps_event_count = max( block->steps[ALPHA_STEPPER], max( block->steps[BETA_STEPPER], block->steps[GAMMA_STEPPER] ) );
  65
  66     block->millimeters = distance;
  67     double inverse_millimeters = 0;
  68     if( distance > 0 ){ inverse_millimeters = 1.0/distance; }
  69
  70     // Calculate speed in mm/minute for each axis. No divide by zero due to previous checks.
  71     // NOTE: Minimum stepper speed is limited by MINIMUM_STEPS_PER_MINUTE in stepper.c
  72     double inverse_minute = feed_rate * inverse_millimeters;
  73     if( distance > 0 ){
  74         block->nominal_speed = block->millimeters * inverse_minute;           // (mm/min) Always > 0
  75         block->nominal_rate = ceil(block->steps_event_count * inverse_minute); // (step/min) Always > 0
  76     }else{
  77         block->nominal_speed = 0;
  78         block->nominal_rate = 0;
  79     }
  80
  81     // Compute the acceleration rate for the trapezoid generator. Depending on the slope of the line
  82     // average travel per step event changes. For a line along one axis the travel per step event
  83     // is equal to the travel/step in the particular axis. For a 45 degree line the steppers of both
  84     // axes might step for every step event. Travel per step event is then sqrt(travel_x^2+travel_y^2).
  85     // To generate trapezoids with contant acceleration between blocks the rate_delta must be computed
  86     // specifically for each line to compensate for this phenomenon:
  87     // Convert universal acceleration for direction-dependent stepper rate change parameter
  88     block->rate_delta = (float)( ( block->steps_event_count*inverse_millimeters * this->acceleration ) / ( THEKERNEL->stepper->acceleration_ticks_per_second * 60 ) ); // (step/min/acceleration_tick)
  89
  90     // Compute path unit vector
  91     double unit_vec[3];
  92     unit_vec[X_AXIS] = deltas[X_AXIS]*inverse_millimeters;
  93     unit_vec[Y_AXIS] = deltas[Y_AXIS]*inverse_millimeters;
  94     unit_vec[Z_AXIS] = deltas[Z_AXIS]*inverse_millimeters;
  95
  96     // Compute maximum allowable entry speed at junction by centripetal acceleration approximation.
  97     // Let a circle be tangent to both previous and current path line segments, where the junction
  98     // deviation is defined as the distance from the junction to the closest edge of the circle,
  99     // colinear with the circle center. The circular segment joining the two paths represents the
 100     // path of centripetal acceleration. Solve for max velocity based on max acceleration about the
 101     // radius of the circle, defined indirectly by junction deviation. This may be also viewed as
 102     // path width or max_jerk in the previous grbl version. This approach does not actually deviate
 103     // from path, but used as a robust way to compute cornering speeds, as it takes into account the
 104     // nonlinearities of both the junction angle and junction velocity.
 105     double vmax_junction = MINIMUM_PLANNER_SPEED; // Set default max junction speed
 106
 107     if (THEKERNEL->conveyor->queue.size() > 1 && (this->previous_nominal_speed > 0.0)) {
 108       // Compute cosine of angle between previous and current path. (prev_unit_vec is negative)
 109       // NOTE: Max junction velocity is computed without sin() or acos() by trig half angle identity.
 110       double cos_theta = - this->previous_unit_vec[X_AXIS] * unit_vec[X_AXIS]
 111                          - this->previous_unit_vec[Y_AXIS] * unit_vec[Y_AXIS]
 112                          - this->previous_unit_vec[Z_AXIS] * unit_vec[Z_AXIS] ;
 113
 114       // Skip and use default max junction speed for 0 degree acute junction.
 115       if (cos_theta < 0.95) {
 116         vmax_junction = min(this->previous_nominal_speed,block->nominal_speed);
 117         // Skip and avoid divide by zero for straight junctions at 180 degrees. Limit to min() of nominal speeds.
 118         if (cos_theta > -0.95) {
 119           // Compute maximum junction velocity based on maximum acceleration and junction deviation
 120           double sin_theta_d2 = sqrt(0.5*(1.0-cos_theta)); // Trig half angle identity. Always positive.
 121           vmax_junction = min(vmax_junction,
 122             sqrt(this->acceleration * this->junction_deviation * sin_theta_d2/(1.0-sin_theta_d2)) );
 123         }
 124       }
 125     }
 126     block->max_entry_speed = vmax_junction;
 127
 128     // Initialize block entry speed. Compute based on deceleration to user-defined MINIMUM_PLANNER_SPEED.
 129     double v_allowable = this->max_allowable_speed(-this->acceleration,0.0,block->millimeters); //TODO: Get from config
 130     block->entry_speed = min(vmax_junction, v_allowable);
 131
 132     // Initialize planner efficiency flags
 133     // Set flag if block will always reach maximum junction speed regardless of entry/exit speeds.
 134     // If a block can de/ac-celerate from nominal speed to zero within the length of the block, then
 135     // the current block and next block junction speeds are guaranteed to always be at their maximum
 136     // junction speeds in deceleration and acceleration, respectively. This is due to how the current
 137     // block nominal speed limits both the current and next maximum junction speeds. Hence, in both
 138     // the reverse and forward planners, the corresponding block junction speed will always be at the
 139     // the maximum junction speed and may always be ignored for any speed reduction checks.
 140     if (block->nominal_speed <= v_allowable) { block->nominal_length_flag = true; }
 141     else { block->nominal_length_flag = false; }
 142     block->recalculate_flag = true; // Always calculate trapezoid for new block
 143
 144     // Update previous path unit_vector and nominal speed
 145     memcpy(this->previous_unit_vec, unit_vec, sizeof(unit_vec)); // previous_unit_vec[] = unit_vec[]
 146     this->previous_nominal_speed = block->nominal_speed;
 147
 148     // Update current position
 149     memcpy(this->position, target, sizeof(int)*3);
 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 }
 158
 159
 160 // Recalculates the motion plan according to the following algorithm:
 161 //
 162 // 1. Go over every block in reverse order and calculate a junction speed reduction (i.e. block_t.entry_factor)
 163 // so that:
 164 //   a. The junction jerk is within the set limit
 165 //   b. No speed reduction within one block requires faster deceleration than the one, true constant
 166 //      acceleration.
 167 // 2. Go over every block in chronological order and dial down junction speed reduction values if
 168 //   a. The speed increase within one block would require faster accelleration than the one, true
 169 //      constant acceleration.
 170 //
 171 // When these stages are complete all blocks have an entry_factor that will allow all speed changes to
 172 // be performed using only the one, true constant acceleration, and where no junction jerk is jerkier than
 173 // the set limit. Finally it will:
 174 //
 175 // 3. Recalculate trapezoids for all blocks.
 176 //
 177 void Planner::recalculate() {
 178     RingBuffer<Block,32>* queue = &THEKERNEL->conveyor->queue;
 179
 180     int newest = queue->prev_block_index(queue->head);
 181     int oldest = queue->tail;
 182
 183     int block_index = newest;
 184
 185     Block* previous;
 186     Block* current;
 187     Block* next;
 188
 189     current = &queue->buffer[block_index];
 190     current->recalculate_flag = true;
 191
 192     // if there's only one block in the queue, we fall through both while loops and this ends up in current
 193     // so we must set it here, or perform conditionals further down. this is easier
 194     next = current;
 195
 196     while ((block_index != oldest) && (current->recalculate_flag))
 197     {
 198         block_index = queue->prev_block_index(block_index);
 199
 200         next = current;
 201         current = &queue->buffer[block_index];
 202
 203         current->recalculate_flag = false;
 204
 205         current->reverse_pass(next);
 206     }
 207
 208     previous = current;
 209     current = next;
 210
 211     // Recalculates the trapezoid speed profiles for flagged blocks in the plan according to the
 212     // entry_speed for each junction and the entry_speed of the next junction. Must be called by
 213     // planner_recalculate() after updating the blocks. Any recalulate flagged junction will
 214     // compute the two adjacent trapezoids to the junction, since the junction speed corresponds
 215     // to exit speed and entry speed of one another.
 216     while (block_index != newest)
 217     {
 218         current->forward_pass(previous);
 219
 220         // Recalculate if current block entry or exit junction speed has changed.
 221         if (previous->recalculate_flag || current->recalculate_flag )
 222         {
 223             previous->calculate_trapezoid( previous->entry_speed/previous->nominal_speed, current->entry_speed/previous->nominal_speed );
 224             previous->recalculate_flag = false;
 225         }
 226
 227         block_index = queue->next_block_index(block_index);
 228         previous = current;
 229         current = &queue->buffer[block_index];
 230     }
 231
 232     // Last/newest block in buffer. Exit speed is set with MINIMUM_PLANNER_SPEED. Always recalculated.
 233     current->calculate_trapezoid( current->entry_speed/current->nominal_speed, MINIMUM_PLANNER_SPEED/current->nominal_speed );
 234     current->recalculate_flag = false;
 235 }
 236
 237 // Debug function
 238 void Planner::dump_queue(){
 239     for( int index = 0; index <= THEKERNEL->conveyor->queue.size()-1; index++ ){
 240        if( index > 10 && index < THEKERNEL->conveyor->queue.size()-10 ){ continue; }
 241        THEKERNEL->streams->printf("block %03d > ", index);
 242        THEKERNEL->conveyor->queue.get_ref(index)->debug();
 243     }
 244 }
 245
 246 // Calculates the maximum allowable speed at this point when you must be able to reach target_velocity using the
 247 // acceleration within the allotted distance.
 248 double Planner::max_allowable_speed(double acceleration, double target_velocity, double distance) {
 249   return(
 250     sqrt(target_velocity*target_velocity-2L*acceleration*distance)  //Was acceleration*60*60*distance, in case this breaks, but here we prefer to use seconds instead of minutes
 251   );
 252 }
 253
 254