Re: [robocup-rescue-s] Blocked agents

From: Arash Rahimi <rahimi@ce.aut.ac.ir>
Date: Thu 03 Nov 2005 - 08:32:37 GMT

Dear David,

The problem you are facing is a common problem in RoboCup
Rescue Simulation environment and is called 'Traffic Jam'
in the community. The main reason for this phenomenon is
the traffic rules imposed by traffic simulator. In detail,
each road has a number of lines to head, and a number of
lines to tail.

Consider a road r that has L(r, h) (resp. to L(r, t)) lines
to head (resp. tail) with L_f(r, h) (resp. L_f(r, t)) open
and free lines out of L(r, h) (resp. L(r, t)) lines to head
(resp. tail).

Rule #1: Two automobiles(agents) which are on the same
line of the same road should have a minimum distance of
5m with each other.

Rule #2: An automobile entering a road chooses the line
with the maximum capacity and goes to that line while
keeping rule #1.

So, the maximum number of agents that can enter a road
from its head node is:

max_entering(r, h) = L_f(r,t) * C(r) + (L(r,t) - L_f(r,t)) * C_B(r)

Where C(r) is capacity of one free line of road r which
is:

C(r) = Length(r) / 5000 + 1

and C_B(r) is the capacity of one blocked line of road r
which is:

C_B(r) = Length(r) / 10000 + 1

The same formula can be used for finding the maximum number
of agents that can enter a road from its tail node:

max_entering(r, t) = L_f(r,h) * C(r) + (L(r,h) - L_f(r,h)) * C_B(r)

You can see that if some agents enter from the head node and
some of them enter from the tail node, they can make use of
almost twice the capacity comparing to the case when all of
them enter from the same node.

Now, if you would like to fill the road with its maximum
capacity while keeping place for other agents to pass the
road, you can substitue L_f(r, t) (resp. L_f(r, h)) with
L_f(r, t) - 1 (resp. L_f(r, h) - 1) in the formulas above.

This is the simplest solution to this problem. But keeping
in mind the fact that most of the roads has only one line
to head (resp. to tail), this solution does not give an
acceptable result.

Yes! Extinguishing from a building is a good idea. Note that
the maximum number of fire brigades who can be in a building
at the same time is 1.

Of course, In the case the 'Traffic Jam' happens, your agent
should detect and eliminate it. Simply, It can be done by
checking if your agent has sent an AK_MOVE command in the
last cycle and its position is not changed in the current
cycle. If this case happens, your agent can consider this
road as a blocked road temporarily and tries to find a path
to its destination that does not make use of this road. Note
that there are two kind of traffic jams, Road to Node, and
Node to road. Capacity of a node is the same as capacity of
the road using which your agent enters that node. So, it
can be concluded that entering from different roads attached
to a node increases the capacity of that node.

Unfortunately, Communication is not a good way to eliminate
a traffic jam due to its delay.

To keep your ideas fresh, I do not list the other effective
solutions to this problem. I hope the above words would be
a good introduction to this problem.

Regards,
Arash Rahimi

>
> I was wondering if anyone could help me with this problem:
> it is very common for me that two or more agents want to move to the same
> Road and they block themselves, losing a lot of cycles.
> Sometimes the agents get blocked because a some firebrigadse are
> extinguishing from
> that Road.
>
> I have thought some solutions:
> - extinguish from a Building whenever possible
> - detect when the agent could not move and do domething else (not sure
> what to do exactly)
> - all agents say their position so any agent can hear nearby agents and
> detect heavy traffic
> can anyone tell me how many agents can be in a Road/Node/Building at the
> same time?
>
> Does anyone have any other idea?
>
> Thanks,
> David
>
> --
> David Ojeda A
> david@ac.labf.usb.ve | david@gia.usb.ve
> Linux Registered User #355562
>
> _______________________________________________
> robocup-rescue-s mailing list
> robocup-rescue-s@mailman.cc.gatech.edu
> https://mailman.cc.gatech.edu/mailman/listinfo/robocup-rescue-s
>

_______________________________________________
robocup-rescue-s mailing list
robocup-rescue-s@mailman.cc.gatech.edu
https://mailman.cc.gatech.edu/mailman/listinfo/robocup-rescue-s
Received on Thu Nov 03 09:58:47 2005

This archive was generated by hypermail 2.1.8 : Thu 03 Nov 2005 - 08:58:48 GMT