Optimal algorithm to move a a rope from one position to another

Question

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

1. Only one actuator may be moved at a time
2. An actuator may be moved any distance, but
3. 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"

Answer 1

Your bolded question What is the optimal algorithm is off-topic for Code Review. If you're really interested in original-research answers to that question, I think it might plausibly be on-topic for Puzzling SE or Computer Science SE.

Certainly if you post in either of those places, looking for "optimal" algorithms, you will have to define what you mean by "optimal." The simplest way of doing that would also be useful on CodeReview — and also in general in your programming career! Provide test cases.

assert solve([2, 4, 6, 3], [-2, -4, -6, -3], 3) == 42

This test case was constructed by looking at your sample program and then filling in an utterly random number 42 in the one place that matters. When you post the question elsewhere (and/or here again), make sure to have that number filled in. And then give some other test cases!

assert solve([2, 4, 6, 3], [-2, -4, -6, -3], float('inf')) == 4
assert solve([1, 1, 1], [0, 0, 0], 1) == 3

And then consider what should happen in cases of "invalid input":

assert solve([1, 1, 1], [0, 0, 0], 0) is None
assert solve([1, 2, 1], [1, 3, 1], 1) is None
assert solve([1, 3, 1], [1, 2, 1], 1) is None
assert solve([1, 3, 1], [1, 3, 1], 1) is None

---

On your code itself, try to write out full identifiers instead of abbreviations: index (index of what?) instead of ind, for example.

When writing a "predicate" function that returns bool, give it a name that indicates the predicate, rather than an action verb: instead of check_legal (which should really be check_legality), prefer is_legal, so that you can write

assert is_legal(init, max_dist)

Notice that max_dist has no reason to be a keyword argument, and no reason to be optional. Instead of passing None and special-casing it, just pass float('inf') and don't write any special cases.

---

pos_options = [final[ind]]\
                  +[n+sign*max_dist for n in neighbors]

This line of code is impenetrable, due to the lack of whitespace and the backslash in the middle. I'd at least recommend

pos_options = [final[ind]] + [n + sign * max_dist for n in neighbors]

and then look for a way to refactor that or at least put a code comment explaining the logic behind the expression.