Early idea

Back to: PRE2015_2_Groep1
In this page we give a first sketch of the test case and approach we are considering.

Scenario

We will consider the following test case: In a bounded area of operation (AO) several piles of material are present, which should be transported to some clear zone (CZ). The piles can be thought of piles of ruin in some disaster-struck area which either need to be cleared, or are in the way of rescuing a person. Each pile consists of one or more blocks of various size. Some blocks can be moved by an individual robot, some are so large more robots are needed to move them. Every block needs to be moved to the CZ by the swarm which operates from the CZ.

Example overview of the test case with Area of Operation (AO), Clear Zone (CZ) and three piles.

Example of what pile 1 might look like. The numbers in the blocks indicate the number of robots necessary to move the block.

• The green shapes indicate pieces of material, the number inside shows how much robots are needed to move it outside of the box.
• The yellow shapes indicate obstacles which can't be moved, and therefore have to be evaded.
• The blue shapes indicate the piles (groups) of material

Subroutines

The following subroutines are necessary in order to clear the AO:

• Search for piles
• Assign robots to piles
• Move to piles
• Assign robots to blocks
• Move blocks

For the search, one of a number of swarm search algorithms might be applied. Then, once piles are found a division needs to be made: some robots should - up until some point - keep searching for more piles, others need to be assigned to piles. This assignment can be done trough a pheromone based approach (see literature study - More specific references will come soon), a path needs to be found - this can be done partly by the pheromone based approach, but we might need some shortest path algorithm to ensure optimality in a changing AO (since piles vanish, the shortest path might change) - and once a robot arrives at a pile, assignment to a block needs to be done. If no robots are in need of help at the pile of arrival, the new arrival can be assigned to a random - or simply the closest - block, if a robot is assigned to a block it can't move alone, another pheromone can be used to communicate the need of assistance, and the first pheromone can be increased for the pile to ensure enough robots arrive at the pile to assist. To prevent situations in which all robots are assigned to blocks that can't be moved by the robots, some mechanism should be implemented to make robots give up after a certain time.

For the moving of the blocks, more complex individual behaviour might need to be implemented for scenario's in which not only blocks, but also victims are present at a pile: victims need to be handled with more care, and should be handled with more care. Furthermore, in any scenario, the moving of a large block might need more coordination than just assignment.