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 #include "mbed.h"
  11 #include "libs/nuts_bolts.h"
  12 #include "libs/RingBuffer.h"
  13 #include "../communication/utils/Gcode.h"
  14 #include "libs/Module.h"
  15 #include "libs/Kernel.h"
  16 #include "Block.h"
  17 #include "Planner.h"
  18
  19
  20
  21 Planner::Planner(){
  22     clear_vector(this->position);
  23     clear_vector_double(this->previous_unit_vec);
  24     this->previous_nominal_speed = 0.0;
  25     this->has_deleted_block = false;
  26 }
  27
  28 void Planner::on_module_loaded(){
  29     this->on_config_reload(this);
  30 }
  31
  32 void Planner::on_config_reload(void* argument){
  33     this->acceleration =       this->kernel->config->value(acceleration_checksum       )->required()->as_number();
  34     this->max_jerk =           this->kernel->config->value(max_jerk_checksum           )->required(      )->as_number();
  35     this->junction_deviation = this->kernel->config->value(junction_deviation_checksum )->by_default(0.05)->as_number();
  36 }
  37
  38
  39 // Append a block to the queue, compute it's speed factors
  40 void Planner::append_block( int target[], double feed_rate, double distance, double deltas[] ){
  41
  42     // Do not append block with no movement
  43     //if( target[ALPHA_STEPPER] == this->position[ALPHA_STEPPER] && target[BETA_STEPPER] == this->position[BETA_STEPPER] && target[GAMMA_STEPPER] == this->position[GAMMA_STEPPER] ){ this->computing = false; return; }
  44
  45     // Stall here if the queue is ful
  46     while( this->queue.size() >= this->queue.capacity() ){ wait_us(100); }
  47
  48     // Clean up the vector of commands in the block we are about to replace
  49     // It is quite strange to do this here, we really should do it inside Block->pop_and_execute_gcode
  50     // but that function is called inside an interrupt and thus can break everything if the interrupt was trigerred during a memory access
  51     Block* block = this->queue.get_ref( this->queue.size()-1 );
  52     if( block->planner == this ){
  53         for(short index=0; index<block->commands.size(); index++){
  54             block->commands.pop_back();
  55             block->travel_distances.pop_back();
  56         }
  57     }
  58
  59     this->queue.push_back(Block());
  60     block = this->queue.get_ref( this->queue.size()-1 );
  61     block->planner = this;
  62
  63     this->computing = true; //TODO: Check if this is necessary
  64
  65     // Direction bits
  66     block->direction_bits = 0;
  67     char direction_bits[3] = {this->kernel->stepper->alpha_dir_pin, this->kernel->stepper->beta_dir_pin, this->kernel->stepper->gamma_dir_pin};
  68     for( int stepper=ALPHA_STEPPER; stepper<=GAMMA_STEPPER; stepper++){
  69         if( target[stepper] < position[stepper] ){ block->direction_bits |= (1<<direction_bits[stepper]); }
  70     }
  71
  72     // Number of steps for each stepper
  73     for( int stepper=ALPHA_STEPPER; stepper<=GAMMA_STEPPER; stepper++){ block->steps[stepper] = labs(target[stepper] - this->position[stepper]); }
  74
  75
  76     // Max number of steps, for all axes
  77     block->steps_event_count = max( block->steps[ALPHA_STEPPER], max( block->steps[BETA_STEPPER], block->steps[GAMMA_STEPPER] ) );
  78     //if( block->steps_event_count == 0 ){ this->computing = false; return; }
  79
  80     block->millimeters = distance;
  81     double inverse_millimeters = 0;
  82     if( distance > 0 ){ inverse_millimeters = 1.0/distance; }
  83
  84     // Calculate speed in mm/minute for each axis. No divide by zero due to previous checks.
  85     // NOTE: Minimum stepper speed is limited by MINIMUM_STEPS_PER_MINUTE in stepper.c
  86     double inverse_minute = feed_rate * inverse_millimeters;
  87     if( distance > 0 ){
  88         block->nominal_speed = block->millimeters * inverse_minute;           // (mm/min) Always > 0
  89         block->nominal_rate = ceil(block->steps_event_count * inverse_minute); // (step/min) Always > 0
  90     }else{
  91         block->nominal_speed = 0;
  92         block->nominal_rate = 0;
  93     }
  94
  95     //this->kernel->serial->printf("nom_speed: %f nom_rate: %u step_event_count: %u block->steps_z: %u \r\n", block->nominal_speed, block->nominal_rate, block->steps_event_count, block->steps[2]  );
  96
  97     // Compute the acceleration rate for the trapezoid generator. Depending on the slope of the line
  98     // average travel per step event changes. For a line along one axis the travel per step event
  99     // is equal to the travel/step in the particular axis. For a 45 degree line the steppers of both
 100     // axes might step for every step event. Travel per step event is then sqrt(travel_x^2+travel_y^2).
 101     // To generate trapezoids with contant acceleration between blocks the rate_delta must be computed
 102     // specifically for each line to compensate for this phenomenon:
 103     // Convert universal acceleration for direction-dependent stepper rate change parameter
 104     block->rate_delta = ceil( block->steps_event_count*inverse_millimeters * this->acceleration*60.0 / this->kernel->stepper->acceleration_ticks_per_second ); // (step/min/acceleration_tick)
 105
 106
 107     // Compute path unit vector
 108     double unit_vec[3];
 109     unit_vec[X_AXIS] = deltas[X_AXIS]*inverse_millimeters;
 110     unit_vec[Y_AXIS] = deltas[Y_AXIS]*inverse_millimeters;
 111     unit_vec[Z_AXIS] = deltas[Z_AXIS]*inverse_millimeters;
 112
 113     // Compute maximum allowable entry speed at junction by centripetal acceleration approximation.
 114     // Let a circle be tangent to both previous and current path line segments, where the junction
 115     // deviation is defined as the distance from the junction to the closest edge of the circle,
 116     // colinear with the circle center. The circular segment joining the two paths represents the
 117     // path of centripetal acceleration. Solve for max velocity based on max acceleration about the
 118     // radius of the circle, defined indirectly by junction deviation. This may be also viewed as
 119     // path width or max_jerk in the previous grbl version. This approach does not actually deviate
 120     // from path, but used as a robust way to compute cornering speeds, as it takes into account the
 121     // nonlinearities of both the junction angle and junction velocity.
 122     double vmax_junction = MINIMUM_PLANNER_SPEED; // Set default max junction speed
 123
 124     if (this->queue.size() > 1 && (this->previous_nominal_speed > 0.0)) {
 125       // Compute cosine of angle between previous and current path. (prev_unit_vec is negative)
 126       // NOTE: Max junction velocity is computed without sin() or acos() by trig half angle identity.
 127       double cos_theta = - this->previous_unit_vec[X_AXIS] * unit_vec[X_AXIS]
 128                          - this->previous_unit_vec[Y_AXIS] * unit_vec[Y_AXIS]
 129                          - this->previous_unit_vec[Z_AXIS] * unit_vec[Z_AXIS] ;
 130
 131       // Skip and use default max junction speed for 0 degree acute junction.
 132       if (cos_theta < 0.95) {
 133         vmax_junction = min(this->previous_nominal_speed,block->nominal_speed);
 134         // Skip and avoid divide by zero for straight junctions at 180 degrees. Limit to min() of nominal speeds.
 135         if (cos_theta > -0.95) {
 136           // Compute maximum junction velocity based on maximum acceleration and junction deviation
 137           double sin_theta_d2 = sqrt(0.5*(1.0-cos_theta)); // Trig half angle identity. Always positive.
 138           vmax_junction = min(vmax_junction,
 139             sqrt(this->acceleration*60*60 * this->junction_deviation * sin_theta_d2/(1.0-sin_theta_d2)) );
 140         }
 141       }
 142     }
 143     block->max_entry_speed = vmax_junction;
 144
 145     // Initialize block entry speed. Compute based on deceleration to user-defined MINIMUM_PLANNER_SPEED.
 146     double v_allowable = this->max_allowable_speed(-this->acceleration,0.0,block->millimeters); //TODO: Get from config
 147     block->entry_speed = min(vmax_junction, v_allowable);
 148
 149     // Initialize planner efficiency flags
 150     // Set flag if block will always reach maximum junction speed regardless of entry/exit speeds.
 151     // If a block can de/ac-celerate from nominal speed to zero within the length of the block, then
 152     // the current block and next block junction speeds are guaranteed to always be at their maximum
 153     // junction speeds in deceleration and acceleration, respectively. This is due to how the current
 154     // block nominal speed limits both the current and next maximum junction speeds. Hence, in both
 155     // the reverse and forward planners, the corresponding block junction speed will always be at the
 156     // the maximum junction speed and may always be ignored for any speed reduction checks.
 157     if (block->nominal_speed <= v_allowable) { block->nominal_length_flag = true; }
 158     else { block->nominal_length_flag = false; }
 159     block->recalculate_flag = true; // Always calculate trapezoid for new block
 160
 161     // Update previous path unit_vector and nominal speed
 162     memcpy(this->previous_unit_vec, unit_vec, sizeof(unit_vec)); // previous_unit_vec[] = unit_vec[]
 163     this->previous_nominal_speed = block->nominal_speed;
 164
 165     memcpy(this->position, target, sizeof(int)*3);
 166     this->recalculate();
 167     this->computing = false;
 168     block->computed = true;
 169
 170     this->kernel->call_event(ON_STEPPER_WAKE_UP, this);
 171 }
 172
 173 // Gcodes are attached to their respective block in the queue so that the on_gcode_execute event can be called with the gcode when the block is executed
 174 void Planner::attach_gcode_to_queue(Gcode* gcode){
 175     //If the queue is empty, execute immediatly, otherwise attach to the last added block
 176     if( this->queue.size() == 0 ){
 177         this->kernel->call_event(ON_GCODE_EXECUTE, gcode );
 178     }else{
 179         this->queue.get_ref( this->queue.size() - 1 )->append_gcode(gcode);
 180     }
 181 }
 182
 183
 184
 185 // Recalculates the motion plan according to the following algorithm:
 186 //
 187 // 1. Go over every block in reverse order and calculate a junction speed reduction (i.e. block_t.entry_factor)
 188 // so that:
 189 //   a. The junction jerk is within the set limit
 190 //   b. No speed reduction within one block requires faster deceleration than the one, true constant
 191 //      acceleration.
 192 // 2. Go over every block in chronological order and dial down junction speed reduction values if
 193 //   a. The speed increase within one block would require faster accelleration than the one, true
 194 //      constant acceleration.
 195 //
 196 // When these stages are complete all blocks have an entry_factor that will allow all speed changes to
 197 // be performed using only the one, true constant acceleration, and where no junction jerk is jerkier than
 198 // the set limit. Finally it will:
 199 //
 200 // 3. Recalculate trapezoids for all blocks.
 201 //
 202 void Planner::recalculate() {
 203    this->reverse_pass();
 204    this->forward_pass();
 205    this->recalculate_trapezoids();
 206 }
 207
 208 // Planner::recalculate() needs to go over the current plan twice. Once in reverse and once forward. This
 209 // implements the reverse pass.
 210 void Planner::reverse_pass(){
 211      // For each block
 212     for( int index = this->queue.size()-1; index > 0; index-- ){  // Skip buffer tail/first block to prevent over-writing the initial entry speed.
 213         this->queue.get_ref(index)->reverse_pass((index==this->queue.size()-1?NULL:this->queue.get_ref(index+1)), (index==0? (this->has_deleted_block?&(this->last_deleted_block):NULL) :this->queue.get_ref(index-1)));
 214     }
 215 }
 216
 217 // Planner::recalculate() needs to go over the current plan twice. Once in reverse and once forward. This
 218 // implements the forward pass.
 219 void Planner::forward_pass() {
 220     // For each block
 221     for( int index = 0; index <= this->queue.size()-1; index++ ){
 222         this->queue.get_ref(index)->forward_pass((index==0?NULL:this->queue.get_ref(index-1)),(index==this->queue.size()-1?NULL:this->queue.get_ref(index+1)));
 223     }
 224 }
 225
 226 // Recalculates the trapezoid speed profiles for flagged blocks in the plan according to the
 227 // entry_speed for each junction and the entry_speed of the next junction. Must be called by
 228 // planner_recalculate() after updating the blocks. Any recalulate flagged junction will
 229 // compute the two adjacent trapezoids to the junction, since the junction speed corresponds
 230 // to exit speed and entry speed of one another.
 231 void Planner::recalculate_trapezoids() {
 232     // For each block
 233     for( int index = 0; index <= this->queue.size()-1; index++ ){ // We skip the first one because we need a previous
 234
 235         if( this->queue.size()-1 == index ){ //last block
 236             Block* last = this->queue.get_ref(index);
 237             last->calculate_trapezoid( last->entry_speed / last->nominal_speed, MINIMUM_PLANNER_SPEED / last->nominal_speed );
 238         }else{
 239             Block* current = this->queue.get_ref(index);
 240             Block* next =    this->queue.get_ref(index+1);
 241             if( current->recalculate_flag || next->recalculate_flag ){
 242                 current->calculate_trapezoid( current->entry_speed/current->nominal_speed, next->entry_speed/current->nominal_speed );
 243                 current->recalculate_flag = false; // Reset current only to ensure next trapezoid is computed
 244             }
 245         }
 246     }
 247 }
 248
 249 // Get the first block in the queue, or return NULL
 250 Block* Planner::get_current_block(){
 251     if( this->queue.size() == 0 ){ return NULL; }
 252     return this->queue.get_ref(0);
 253 }
 254
 255
 256 // We are done with this block, discard it
 257 void Planner::discard_current_block(){
 258     //this->has_deleted_block = true;
 259     //this->queue.get(0,this->last_deleted_block );
 260     this->queue.delete_first();
 261 }
 262
 263 // Debug function
 264 void Planner::dump_queue(){
 265     for( int index = 0; index <= this->queue.size()-1; index++ ){
 266        if( index > 10 && index < this->queue.size()-10 ){ continue; }
 267        this->kernel->serial->printf("block %03d > ", index);
 268        this->queue.get_ref(index)->debug(this->kernel);
 269     }
 270 }
 271
 272
 273
 274 // Calculates the maximum allowable speed at this point when you must be able to reach target_velocity using the
 275 // acceleration within the allotted distance.
 276 double Planner::max_allowable_speed(double acceleration, double target_velocity, double distance) {
 277   return(
 278     sqrt(target_velocity*target_velocity-2L*acceleration*60*60*distance)  //Was acceleration*60*60*distance, in case this breaks, but here we prefer to use seconds instead of minutes
 279   );
 280 }
 281
 282