I'm an engineer working with a deformable membrane that is attached to actuators. The goal is to move the membrane from one shape to another, without ripping the membrane. This imposes "neighbor rules" which state the maximum deviation between neighboring actuators cannot exceed some value, or the membrane will rip.
For the purposes of the problem, let's consider a 1-d membrane or "rope" that is attached to actuators:
The goal is to move the rope from one set of actuator positions to another in the minimum number of moves.
The rules are
- Only one actuator may be moved at a time
- An actuator may be moved any distance, but
- An actuator must respect the neighbor rule, so the distance between it and subsequent actuators cannot exceed a fixed distance
The code below presents two algorithms, neither of which is optimal. The first algorithm,
get_max_deviation_index picks the actuator which is furthest from its final position, then moves it the maximum distance possible. This algorithm gets stuck on a simple test of moving from position [2, 4, 6, 3] to [-2, -4, -6, -3]. The next algorithm,
get_next_index, starts at the first actuator, moves it the maximum distance possible, and then moves to the subsequent actuator and does the same, until it is converged. This algorithm works, but I do not believe it is optimal.
The code below implements both algorithms; please comment in/out the line beginning with
ind = to switch between them. My question is:
What is the optimal algorithm to move between one position and another?
import numpy as np def check_legal(y, max_dist=None): #checks if a position is legal return np.all(np.diff(y)<=max_dist) def get_neighbors(index, array): #gets neighbors of an element in a list, #respecting end nodes max_index = len(array)-1 if index == 0: neighbors = [array[index+ 1]] elif index == max_index: neighbors = [array[index- 1]] else: neighbors = list(array[[index-1, index + 1]]) return neighbors def get_max_deviation_index(current_pos, final): diff = np.abs(final-current_pos) max_ind = np.where(diff == np.max(diff)) #find move amt necessary to get to final position return max_ind def get_next_index(current_pos, current_ind): if current_ind == len(current_pos)-1: next_ind = 0 else: next_ind = current_ind+1 return next_ind def solve(init, final, max_dist=None): assert check_legal(init, max_dist=max_dist) assert check_legal(final, max_dist=max_dist) assert len(init) == len(final) print init current_pos = init idx = 0 ind = 0 while not np.allclose(current_pos, final): #find index that has maximum offset from where it should be #ind = get_max_deviation_index(current_pos, final) ind = get_next_index(current_pos, ind) delta = final[ind]-current_pos[ind] if delta == 0: continue sign = np.sign(delta) #find neighbors of that point neighbors = get_neighbors(ind, current_pos) #find the maximum allowable move pos_options = [final[ind]]\ +[n+sign*max_dist for n in neighbors] if sign<0: move = max(pos_options) else: move = min(pos_options) current_pos[ind] = move print current_pos idx+=1 return idx if __name__ == "__main__": initial_state = np.array([2,4,6, 3]) final_state = -initial_state max_dist = 3 #max distance between neighboring actuators ans = solve(initial_state, final_state, max_dist=max_dist) print "Completed in ", ans, " moves"