Balanced parallel exploration of orthogonal regions (Q2004877): Difference between revisions

From MaRDI portal
Set OpenAlex properties.
ReferenceBot (talk | contribs)
Changed an Item
Property / cites work
 
Property / cites work: A framework for multi-robot node coverage in sensor networks / rank
 
Normal rank
Property / cites work
 
Property / cites work: A Recursive Approach to Multi-robot Exploration of Trees / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q2783190 / rank
 
Normal rank

Revision as of 17:55, 23 July 2024

scientific article
Language Label Description Also known as
English
Balanced parallel exploration of orthogonal regions
scientific article

    Statements

    Balanced parallel exploration of orthogonal regions (English)
    0 references
    0 references
    0 references
    7 October 2020
    0 references
    Summary: We consider the use of multiple mobile agents to explore an unknown area. The area is orthogonal, such that all perimeter lines run both vertically and horizontally. The area may consist of unknown rectangular holes which are non-traversable internally. For the sake of analysis, we assume that the area is discretized into \(N\) points allowing the agents to move from one point to an adjacent one. Mobile agents communicate through face-to-face communication when in adjacent points. The objective of exploration is to develop an online algorithm that will explore the entire area while reducing the total work of all \(k\) agents, where the work is measured as the number of points traversed. We propose splitting the exploration into two alternating tasks, perimeter and room exploration. The agents all begin with the perimeter scan and when a room is found they transition to room scan after which they continue with perimeter scan until the next room is found and so on. Given the total traversable points \(N\), our algorithm completes in total \(O(N)\) work with each agent performing \(O(N/k)\) work, namely the work is balanced. If the rooms are hole-free the exploration time is also asymptotically optimal, \(O(N/k)\). To our knowledge, this is the first agent coordination algorithm that considers simultaneously work balancing and small exploration time.
    0 references
    online algorithm
    0 references
    mobile agents
    0 references
    parallel exploration
    0 references
    limited communication
    0 references
    work balancing
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references