Agents need to be able to navigate with blocks attached to them. #36
Comments
|
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.
Il ven 22 mag 2020, 09:36 Luc Weytingh <notifications@github.com> ha
scritto:
… As of now, agents do not know how to path-find with blocks attached. It
would be great if there is a general solution to this problem.
—
You are receiving this because you are subscribed to this thread.
Reply to this email directly, view it on GitHub
<#36>, or unsubscribe
<https://github.com/notifications/unsubscribe-auth/AAJFMVH4K275ZMTBBL5FJVTRSYTOPANCNFSM4NHR4D3A>
.
|
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 |
|
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. |
|
Perhaps I was not clear,
if you transform all your maps by grouping e.g. 9 cells in one cell.
o = empty,
O = obstacle
X = agent
B = block
O o o
o o o ==> O
o o O
o o o
B X B ===> X
o o o
you can plan in the new map as it was just a simple agent.
there will be configurations possible which are certainly lost, but at
least if there are solutions they will be given tractably.
or am I losing part of the problem?
…On Fri, May 22, 2020 at 12:17 PM Luc Weytingh ***@***.***> wrote:
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.
—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
<#36 (comment)>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/AAJFMVDRXBKENWHXH637RYLRSZGMBANCNFSM4NHR4D3A>
.
|
|
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. |
|
perhaps you could try an hybrid solution. e.g. by constructing two graphs:
one well-defined, one rough (compressed).
[which reminds by the way how humans remember locations.
https://www.researchgate.net/publication/200827817_Cognitive_Maps_Cognitive_Collages_and_Spatial_Mental_Models
]
…On Fri, May 22, 2020 at 1:13 PM Daniel ***@***.***> wrote:
This may also make it harder to merge the Graphs as @dorian4840
<https://github.com/dorian4840> is working on, since each agent with
blocks attached must have it's own graph where these issues are taken into
account.
—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
<#36 (comment)>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/AAJFMVFYWNPY47YE3M5YT7TRSZM7BANCNFSM4NHR4D3A>
.
|
|
I understand what you meant, this solution somewhat looks like what you suggested: https://harablog.wordpress.com/2009/01/29/clearance-based-pathfinding/. |
|
Yes, it is practically the same idea.
…On Fri, May 22, 2020 at 1:23 PM Luc Weytingh ***@***.***> wrote:
I understand what you meant, this solution somewhat looks like what you
suggested:
https://harablog.wordpress.com/2009/01/29/clearance-based-pathfinding/.
—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
<#36 (comment)>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/AAJFMVCTPYG7UUWFE34RGETRSZOC3ANCNFSM4NHR4D3A>
.
|
|
A interesting difference one can notice is that the size of the elements in
the game they considered are fixed while in your case you can change it.
so for instance, if you don't find a path with a cell of 9, you can try to
find it with a cell of 4.
e.g.
from cell of 9 (max 8 blocks?)
o B o
o X B ===> X
o o o
to cell of 4 (max 3 blocks?)
B o
X B ===> X
On Sat, May 23, 2020 at 8:20 AM Giovanni Sileno <giovanni.sileno@gmail.com>
wrote:
… Yes, it is practically the same idea.
On Fri, May 22, 2020 at 1:23 PM Luc Weytingh ***@***.***>
wrote:
> I understand what you meant, this solution somewhat looks like what you
> suggested:
> https://harablog.wordpress.com/2009/01/29/clearance-based-pathfinding/.
>
> —
> You are receiving this because you commented.
> Reply to this email directly, view it on GitHub
> <#36 (comment)>,
> or unsubscribe
> <https://github.com/notifications/unsubscribe-auth/AAJFMVCTPYG7UUWFE34RGETRSZOC3ANCNFSM4NHR4D3A>
> .
>
|
As of now, agents do not know how to path-find with blocks attached. It would be great if there is a general solution to this problem.
The text was updated successfully, but these errors were encountered: