View Original PDF

RoboCup Rescue 2015 – Rescue Simulation League Team Description MRL (Iran)

Pooya Deldar Gohardani, Sajjad Rostami, Siavash Mehrabi, Peyman Ardestani, Mahdi Taherian

Mechatronics Research Laboratory, Islamic Azad University, Qazvin Branch, Qazvin, Iran

http://www.mrl.ir

Abstract In this paper we will describe the preparations we have made to take part in RoboCup 2015. In this competition we are still using K-means and convex-hull and Hungarian algorithm for map clustering and agent optimization allocation to partitions. These methods granted proportional agents distribution around the map without need to passing long path. In order to search, we use of maximal covering location problem. We also did some changes on ambulance decision making to have better estimation in the case of death time and number of needed ambulances to rescue a civilian.

Keywords: RoboCup, Rescue Simulation, K-means, Hungarian, Set Covering

1. Introduction

In 2012[1], 2013[2] and 2014[3] we used several different algorithms for allocating ambulance agents to their goals. Some of mentioned algorithms are: Market Base Algorithm [4] used in 2012, Q-Learning [5] used in 2013 and finally we used Learning Automata [6] in 2014. The performance of these algorithms has improved over time. In 2015, like previous years, we use K-Means algorithm [7] for clustering and partitioning the map, and Hungarian algorithm [8] to assign agents to partitions, Learning Automata [9] for decision making and determining the number of needed agents for a buried civilian. K-Means and Hungarian algorithms granted an optimal distribution for all of the agents. These algorithms also make sure that every agent who is assigned to a specific partition has minimum distance to traverse to reach their assigned partition.

Our massaging system is based on our work in previous years. After some changes that have been done in 2013 on messaging system functionality, we have gained decreased massage size and improved efficiency. In 2014 our focus was on improving efficiency and some changes to improve bandwidth utilization. For 2015 competition we did not apply fundamental changes on messaging system and just focused on utilizing the module and better message types for agents.

In past years, new clear method was introduced for police agents. The method allowed the police agents to remove blockades much faster, but there are some drawbacks to it. For example in some cases it creates dentate blockades, as a result other agents might get trapped inside the blockade. We have tried to overcome this issue with clearing the roads in a way that makes no trap.

We have applied some improvement in fire brigade's decision making algorithm. One of the improvements is on prioritization of tasks. This fairly improved the fire brigades' performance. Searching algorithms is an important factor to find building in fire as well, so we decided to used "Maximal Covering Location Problem" model to improve searching efficiency and minimize agents' traverse. This enables fire brigades to visit more building in less time rather than visiting all buildings one by one.

In this paper we are going to describe aforementioned algorithms and then explain "Maximal Covering Location Problem" that used for fire brigade agents. Finally we will describe our messaging system.

2. Assignment method

Partitioning is one of the basic tasks in rescue simulation system. With partitioning, limited agents are assigned to a specific cluster. This problem is a subset of assignment problem. It is clear that an algorithm is suitable for us only if it fits rescue simulation system characteristics, for example CPU and memory usage.

We can assume that assignment problem is a kind of minimum cost flow problem. We use Hungarian algorithm to assign agents to clusters and Maximal Covering Problem to improve search algorithms. This method enables the agents to perform search task much faster.

2.1. K-means

K-means uses a two-phase iterative algorithm to minimize the sum of point-to-centroid distances, summed over all k clusters:

  • The first phase describes as "batch" updates, where each iteration consists of reassigning points to their nearest cluster centroid, all at once, followed by recalculation of cluster centroids. This phase as providing a fast but potentially only approximate solution as a starting point for the second phase.
  • The second phase describes as "on-line" updates, where points are individually reassigned if doing so will reduce the sum of distances, and cluster centroids are recomputed after each reassignment. Each iteration during this second phase consists of one pass through all the points.

Algorithm 1: Basic K-means Algorithm

  • 1: Select K points as the initial centroid.
  • 2: Repeat
  • 3: From K cluster by assigning all points to the closest centroid.
  • 4: Recompute the centroid of each cluster.
  • 5: Until the centroid don't be change

2.2. Hungarian Algorithm

Hungarian Algorithm [4] is a combinatorial optimization algorithm which solves the assignment problem in polynomial time (O (n 4 )).

Algorithm 2: Hungarian Algorithm

  1. Perform initialization:
    • (a) Begin with an empty matching, =∅.
    • (b) Assign feasible values to the dual variables and and as follows:

$$\forall u_i \in V, \alpha_i = 0$$ (1)

$$\forall u_i \in V, \beta_j = min_i(c_{ij})$$ (2)

  1. Perform n stages of the algorithm, each given by the routine Stage.
  2. Output the matching after the stage: M =.

Stage:

  1. Designate each exposed (unmatched) node in V as the root of a Hungarian tree.
  2. Grow the Hungarian trees rooted at the exposed nodes in the equality sub graph. Designate the indices of nodes encountered in the Hungarian tree by the set ∗ , and the indices of nodes encountered in the Hungarian tree by the set ∗ . If an augmenting path is found, go to step (4). If not, and the Hungarian trees cannot be grown further, proceed to step (3).
  3. Modify the dual variables and as follows to add new edges to the equality sub graph. Then go to step (2) to continue the search for an augmenting path.

$$\theta = \frac{1}{2} \min_{i \in I^, j \notin J^} (c_{ij} - \alpha_i - \beta_j)$$

$$\alpha_i \leftarrow \begin{cases} \alpha_i + \theta & i \in I^* \ \alpha_i - \theta & i \notin I^* \end{cases}$$

$$\beta_j \leftarrow \begin{cases} \beta_i + \theta & j \in J^* \ \beta_i + \theta & j \notin J^* \end{cases}$$

$$\beta_j \leftarrow \begin{cases} \beta_i + \theta & j \in J^* \ \beta_i + \theta & j \notin J^* \end{cases}$$

Augment the current matching by flipping matched and unmatched edges along the selected augmenting path. That is, $M_k$ (the new matching at stage k) is given by $(M_{k-1} - P) \cup (P - M_{k-1})$ , where $M_{k-1}$ is matching from the previous stage and P is the set of edges on the selected augmenting path.

3. Fire Brigade

Based on our experience trough past years, we have changed fire brigades priorities and used new fire search algorithms. For RoboCup 2015, we added capabilities such as predicting building with high fire probability and estimating number of needed agents for firefighting. In these predictions we have considered some factors such as building material, building size and building position. According to aforementioned points, fire brigades agents can do firefighting task more efficient.

4. Police force

Since police agents have a lot of effect on the other agents' performance, most of our attention was dedicated on police agent's coordination and corporation with other agents. At the beginning of using new clear method we have faced several problems. One of these problems was dentate blockades that could trap other agents into a blockade the way that the trapped agent must wait until a police force comes and clear the path for it. It can strongly reduce the agents' performance.

We used Guide Line Strategy in RoboCup 2014, to overcome this issue. According to this strategy, a police agent clears the roads along the guidelines to smoothly clear the road without any residues so that agents can move along faster, without getting stuck.

Another improvement is changing police force priorities. We have prioritized opening the blockades tasks with characteristics such as frequent agent's traffic, centrality and importance of the buildings. Changing priorities improved police performance as well as and other agents'.

Clearing the roads using the guideline
Clearing the roads using the guideline

5. Ambulance Agent

In recent years we used different strategy to coordinate ambulance agents. To do this, we have tested related algorithms such as: Market Based Method, Leader initiator Auction, Market with Obstinate Agent and Q-Learning. The important point is that we must customized mentioned algorithms for rescue simulation system. Each of these algorithms have their positive and negative aspect and according to our tests we decided to combine Market Base Method with Obstinate agents and Learning Automata.

Learning Automata has three different models which are P, Q and S. These models change based on continuous or discrete conditions of results. Although different schemes of LRP, LRI and LReP based on used punishment rate in learning process are available for using. As shown in Fig. 1 location of learning Automata is as same as Q learning, but learning method and updating and used structure in this method will be different. In learning Automata structure for each defined condition in environment we have a vector of available action, if we consider the amount of these actions as 'n' in pure chance condition probability of each condition will be 1/n.

Learning Automata diagram
Learning Automata diagram

References

  1. Deldar Gohardani, P., Ardestani, P., Shabani, M., Mehrabi, S. and Hooshangi, V., RoboCup Rescue 2012, rescue simulation league, team description, MRL (Iran), (2012).
  2. Deldar Gohardani, P., Ardestani, P., Mehrabi, S., Taherian, M., Mirzaei Ramhormozi, S. and Yousefi, M.A., RoboCup Rescue 2013, rescue simulation league, team description, MRL (Iran), (2013).
  3. Deldar Gohardani, P., Ardestani, P., Mehrabi, S., Taherian, M., Shabani, M., Robocup Rescue, rescue simulation league, team description, MRL(Iran), (2014).
  4. Deldar Gohardani, P., Ardestani, P., Masoumi, B., Meybodi, M.R., Mehrabi, S., Coordination of Ambulance Team Agents in Rescue Simulation Using Auction Strategy, International Conference on Affective Computing and Intelligent Iteraction, (2012).
  5. Watkins, C., Q-Learning, Technical Note, Machine Learning, Vol.8, pp.279-292, (1992).
  6. R. S. Sutton, andA. G. Barto, Reinforcement Learning: An introduction. Cambridge, MA: MIT Press, (1998).
  7. Steinbach, M., Karypis, G. and Kumar, V., A Comparison of Document Clustering Techniques, University Of Minnesota, Technical Report, pp. #00-034, (2000).
  8. Kuhn, H. W., The Hungarian method for the assignment problem, naval reaserch logistics quarterly, pp. 83-97, (1955).
  9. Burkard, R., Mauro, D. and Silvano, M., Assignment problem, revised, reprint. Philadelphia: SIAM, (2012).
  10. Wikipedia, Covering Problem, http://en.wikipedia.org/wiki/Covering_problem, (2013).
  11. Wikipedia, Maximum Coverage Problme, http://en.wikipedia.org/wiki/Maximum_coverage_problem, (2014).
  12. Vazirani, V. V., Approximation Algorithms, Springer, ISBN: 978-3-662-04565-7, (2001).
  13. Wikipedia, Set Cover Problem, http://en.wikipedia.org/wiki/Set_cover_problem, (2014).
  14. Church, R. and Revelle, C., The Maximal Covering Location Problem, Journal of Regional Science Association International, Vol. 32, pp. 101-118, (1974).