Home

#Overview

Choose task -> naive plan -> Merge

#Heuristics:

APSP

The all pairs shortest path is calculated at the beginning, and supports

• Check if a position is a wall
• Length of the shortest path between two points not considering agents and boxes (-1 if there is no path)
• Get the naive plan to move, push and pull between two points

Trafic:

Trafic[x,y] contains the number of shortest paths going through cell (x,y), thus estimating if the cell can be used for storage.

TODO

GoalPriority

Floodfilling from each goal, assigning to each cell the minimum of the current value of the cell and the floodfill. The floodfill number is increased each time a goal is reached. This gives an estimate of the goals that lays behind each goal, and is used to prioritize which goals to get first.

#Choose task: ##Available tasks:

• move box
• move agent
• move agent to storage
• move box to storage
• nop Chooses parameters (agent, box, position...) by searching the high-level tree.

Highlevel actions:

An interface with

• desitination() coordinate
• agent() Robot
• previousAction() *highlevelAction
• precondition() int **TODO: goals can be conflicting ** precondition() returns an integer which is:
• -1: The action is impossible
• 0: The action can be executed
• n: n > 0, No lowlevel plan has been found but may exist. n is an estimate for the cost

#Naive plan: Currently this is a series of push/pull/move actions following the shortest path. TODO: This should also have the option of doing an actual search

#Merge: Takes a list with a plan for each agent. Each plan consists of a number of agentActions. The merge algorithm returns a list of joint actions which can be sent to the server or a new precondition if the actions cannot be (or cannot easily be merged). The merger can also TODO add new tasks such as moving a box or agent out of the way.

The plans that are to be merged may have conflicts which can be solved by the merger by the following cases:

Case 0: Insert nop

Insert nops until the plans no longer collides.

Case 1: Box in the way

• Can the agent move the box itself?
• Can the agent easily go around?
• otherwise create a new task to make another agent move it (to a storage area) Maybe this decision can be solved by the highlevel planner, or by a new search tree.

##Case 2: Robot in the way Like before.

###Case 3: Merge by doing a common lowlevel plan search The solution to the conflicting plans is found by doing a lowlevel search among the plans that conflicts. The search begins from a state close to the conflict, and has the goal to get out of the conflict, not to solve the entire highlevel task.

###Case 4: Do a new highlevel search.