Applying Dijkstra Algorithm To Find Lowest Energy Path

Question

I am having a really hard time with the following exercise:

Given a robotic arm that stacks boxes. Boxes must be stacked with a limit of 3 boxes per stack and the order of the boxes must be by weight and placed in the initial boxes (on the left). The robotic arm can stretch one location (+1 space) or all locations (+4 spaces). Consider only the bidirectional context in which the robot uses left and right.

Initial configuration suggestion:

                             | ------
                             |      |
                             | 
_10_  _30_  ____  _10_  ____ | _40_  ____  _20_  ____  _30_

When moving a box, there is a cost of 1 energy. However, moving more than 2 positions costs 75% of the movement. For example: moving a box 4 positions, costs 4*(3/4) = 3 energy. For every 10lbs, the cost increases by 1 energy, so a 20lbs box costs 2. Example: Moving 2 positions a 40lbs box: 2*0.75 + 40/10 = 5.5 energy.

Thus, a possible final configuration would be:

                             | ------
 10    10                    |      |
 30    20                    | 
_40_  _30_  ____  ____  ____ | ____  ____  ____  ____  ____

Use Dijkstra algorithm so that given the initial configuration, the robotic arm can execute the task with the lowest energy expenditure.

Even tough I know how Dijkstra algorithm works, I can't see a way to apply it to the exercise. I think the main problem is that I don't know how to represent the problem as a finite graph. Any tips on how to start solving the exercise would be of great help.

Answer 1

1. Devise a data structure to represent a state ( == graph vertex ). Maybe a list with 10 elements to represent the locations. Each list element is a 3 element list, representing the boxes stacked at that location

2. Given the starting boxes, enumerate all the possible states for those boxes. Prune out states that have more than three boxes in a location or boxes stacked in wrong order.

FOR B in boxes
    FOR L in locations
        IF L has < 3 boxes
            IF top box in L weight >= B weight
                 ADD B to L
                 BREAK from L

3. Devise a method to calculate whether it is possible to move between two states and, if yes, calculate the cost.

4. Add edges between states where move is possible and cost the edge.

5. Devise a method to evaluate a score for each state, approximating how close it is to solution. This can be quite crude. For example: 10 points for each box in first left location, 9 points for each box in second left location, etc.

6. Apply A* algorithm using the state score in step 5 as the heuristic.