I am playing around with ideas to improve the calibration process.
I would like to have the calibration process finish with the machine back in the middle ready to cut something…no restart required.
I want to minimize the number of long moves in the calibration process. Long moves leave more time for the belt to unspool too much and get caught in the gears…so ideally we would end up back at the beginning without any long moves.
The question is: For an MxN gird of points, how do we generate a list of points to move through in the correct order to meet those goals? Does anyone have any ideas for how to do that?
A spiral is the shortest move per step - it is also predictable from a user perspective as they can watch it plus it is reasonably logical from a programmatic perspective.
Seems like a space-filling curve, specifically a hilbert curve would be a good way to do that. Here’s my thought: Allow the user to choose the calibration area (x by y), and a value n to make a nxn an 2^n by 2^n grid hilbert curve. Stretch that grid to the calibration area and you have all the short moves you want. The user would only need to tend the belts for the first long move to the start of the curve.
The only downside here is that it doesn’t return to the center. But I don’t think that’s totally necessary. If the calibration is good, you can do one last calculation to determine where you are from the belt lengths and then move to the center like normal.
Assuming you’re talking about a spiral that starts in the center and spirals out, isn’t that really long moves the farther you get from the center? Forgive my bad drawing, but aren’t the red lengths long moves?
It’s the direction changes and long traverses which I think are the issue - with a spiral that always starts “roughly” in the centre, the first 4 steps will be 100mm and the amount of spooling out will be comparatively small.
Hilbert curves are ok but they aren’t intuitive the the user watching as to where the machine will go next - I’m not sure if there is space in memory for the Maslow to calculate and draw its potential route on screen first and then move through it as that would at least give the user some indication of what will happen when they hit calibrate …?
The spiral seems most intuitive for newbies to understand and anticipate but doesnt it break down for rectangular (non-square) geometries?
I, too, let ChatGPT help me as much as possible. This is its recommended approach given the requirements/constraints.
Me: For a grid of points X wide and y tall, what is an algorithm that would plan a trip to each point, minimize the distance between adjacent points visited, minimizes repeat visits to the same point and ends the trip as close to the center of the grid as possible.
ChatGPT: To solve this problem, we can use a variation of the Traveling Salesman Problem (TSP) called the Rural Postman Problem (RPP) with the added constraint of ending the trip close to the center of the grid. Here’s an algorithm that can be used to plan a trip to each point in the grid while meeting the specified criteria:
Calculate the center of the grid (center_x, center_y).
Calculate the Euclidean distance between each pair of points in the grid and store them in a distance matrix.
Create a list of points to visit, starting with the point closest to the center of the grid.
Initialize a current position variable to the starting point.
While there are unvisited points:
a. Find the nearest unvisited point to the current position.
b. Move to that point and mark it as visited.
c. Update the current position.
Once all points have been visited, return to the center of the grid from the current position.
This algorithm aims to minimize the total distance traveled, avoid repeat visits to the same point, and end the trip as close to the center of the grid as possible. However, please note that finding an optimal solution for this problem is NP-hard, so the algorithm may not always find the absolute shortest path. It provides a heuristic solution that balances the criteria mentioned.
And the javascript implementation of the algorithm:
function euclideanDistance(point1, point2) {
return Math.sqrt(Math.pow(point1[0] - point2[0], 2) + Math.pow(point1[1] - point2[1], 2));
}
function findNearestPoint(currentPosition, unvisitedPoints) {
let minDistance = Infinity;
let nearestPoint = null;
for (let point of unvisitedPoints) {
let distance = euclideanDistance(currentPosition, point);
if (distance < minDistance) {
minDistance = distance;
nearestPoint = point;
}
}
return nearestPoint;
}
function planTrip(gridWidth, gridHeight) {
const centerX = Math.floor(gridWidth / 2);
const centerY = Math.floor(gridHeight / 2);
const centerPoint = [centerX, centerY];
const points = [];
for (let x = 0; x < gridWidth; x++) {
for (let y = 0; y < gridHeight; y++) {
points.push([x, y]);
}
}
const unvisitedPoints = new Set(points.filter(point => !(point[0] === centerX && point[1] === centerY)));
const path = [centerPoint];
let currentPosition = centerPoint;
while (unvisitedPoints.size > 0) {
const nearestPoint = findNearestPoint(currentPosition, unvisitedPoints);
path.push(nearestPoint);
unvisitedPoints.delete(nearestPoint);
currentPosition = nearestPoint;
}
path.push(centerPoint); // Return to the center
return path;
}
// Example usage
const gridWidth = 5;
const gridHeight = 5;
const tripPath = planTrip(gridWidth, gridHeight);
console.log(tripPath);
While it is a solution that should work for any geometry, icdont think it will be consistent an predictable for anyone running the calibration without previous experience. However, if minimizing travel distance solves the need to tend the belts that may not be needed.
Assuming you’re talking about a spiral that starts in the center and spirals out, isn’t that really long moves the farther you get from the center? Forgive my bad drawing, but aren’t the red lengths long moves?
Couldn’t David’s suggestion of calibrating every 100mm to break up the long moves could be generally applied to any long move whether calibrating or not, until the machine is properly calibrated?
