## 1 Introduction  
The exploration problem is a fundamental subject in autonomous mobile robotics that deals with achieving the complete coverage of a previously unknown environment. There are several scenarios where completing exploration of a zone is a central part of the mission, e.g., planetary exploration, reconnaissance, search and rescue, agriculture, cleaning, or dangerous places as mined lands and radioactive zones. Additionally, due to the inner qualities--mainly efficiency and robustness--of multi-robot systems, exploration is usually done cooperatively [1]. Schematically, the exploration of an environment can be seen as the composition of _Mapping_ and _Motion Planning_ tasks. A map is needed in order to plan new motions. Moreover, choosing a correct motion sequence based on this map is also needed to expand the knowledge about the environment optimally. Consequently, _Mapping_ is regularly interleaved with _Motion Planning_, and vice versa, during the whole process [1; 2; 3]. Given that the lack of knowledge is essentially inherent to exploration missions, the best choice for the robots is to visit the places where the gain of information can be potentially higher. The _Task Identification_ problem concerns the identification of the points of interest that should be visited next. It strongly depends on both the sensory robot capabilities and the underlying environment representation. The most widely used representation for this purpose is the well-known _Occupancy Grid_ structure [4]. Based on it, a method to identify points of interest was proposed by [5]. The strategy assumes that the closer to the frontier between known and unknown regions the tasks are defined, the more information the team can gather. Since then, the majority of exploration proposals has adopted this scheme known as _Frontier Points_ or _Frontier Regions_[6; 7; 8]. When multiple robots are involved, it is advisable to avoid several of them moving to the same place. The _Task Allocation_ problem concerns the search for a distribution of tasks to robots that maximises the overall system utility and minimises the amount of overlapped information obtained by the robots [1; 9; 10]. There exist a wide variety of proposed solutions to this problem where a family of methods based on market economies are probably the most popular ones. These methods are based on the notion of _Auctions_ from which the robots can bid for the tasks to decide who goes to where at each moment. The market may be managed centrally either by a virtual agent at the base station as in [3] where the bids are processed centralised by a greedy algorithm or by a robotic agent as in [1]. Conversely, the fleet can manage to exchange the bids among all the members in order to take decentralised decisions [11; 12], avoiding, in turn, the single point of failure. All these methods owe their popularity to their simplicity and ease of implementation, but they suffer from a significant shortcoming: falling in local minima [13]. Far from economy inspired approaches, a scheduling based approach is presented in [2]. This method combines an environment segmentation technique with the centralised task allocation method proposed by [14]. The exploration is performed after dividing the environment into disjoint segments. Thus, the expected sensory overlap between agents is decreased as much as possible. In [15] the authors address coordination implicitly through localisation data exchanging. Robots are forced to wait for others before making a decision. Task selection is made iteratively--one robot after another--employing an objective function which rewards the right choices. In [16] a centralised approach is used. The tasks-to-robots distribution is computed balancing information gain, localisation quality, and navigation costs. Another centralised approach computes a utility function enabling the robots to locally prioritise the tasks within its scope and, potentially, also enabling the whole team to search for the best global distribution as well [9].