Agents need to be able to navigate with blocks attached to them. about mapc-uva HOT 9 CLOSED

from mapc-uva.

A rough solution would be to make the planning on a coarser map, decreasing the definition so that an agent plus blocks count as a full position.

I agree with this theoretically. The only downside to this solution, however, is that we would have to search the entire map for obstacles and expand the obstacles in the direction of attached blocks for an agent. This could be computationally intensive.

Another possibility could be to only path plan normally, but when computing the transition costs to a certain node, the nodes relative to that node corresponding with the relative block attachments could be checked.

i.e. (simplified)

def transition_cost(from, to):
    for node in [from, to] + relative_attached:
        if node is obstacle:
            return inf

    return 1

from mapc-uva.

As it turns out, checking the neighbours for every possible next node is very computationally intensive too. Perhaps I could instead only check the final path for 'if it is possible' and turn if it is not.

from mapc-uva.

from mapc-uva.

This may also make it harder to merge the Graphs as @dorian4840 is working on, since each agent with blocks attached must have it's own graph where these issues are taken into account.

from mapc-uva.

from mapc-uva.

I understand what you meant, this solution somewhat looks like what you suggested: https://harablog.wordpress.com/2009/01/29/clearance-based-pathfinding/.

from mapc-uva.

from mapc-uva.

from mapc-uva.