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))[0][0]
#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"