View in EDS PDF Full Text

Multi-agent pathfinding in the crowded environment with obstacles: Algorithms and experimentation system.

Saved in:
Bibliographic Details
Title: Multi-agent pathfinding in the crowded environment with obstacles: Algorithms and experimentation system.
Authors: Hudziak, Mariusz1, Pozniak-Koszalka, Iwona1, Koszalka, Leszek1 leszek.koszalka@pwr.edu.pl, Kasprzak, Andrzej1
Source: Journal of Intelligent & Fuzzy Systems. 2017, Vol. 32 Issue 2, p1561-1573. 13p.
Subjects: Parallel scheduling (Computer scheduling), Sequential scheduling, Parallel algorithms, Distributed algorithms, Algorithmic randomness
Abstract: The objective of this paper is to give a tool for the practical users, looking for the efficient way for solving pathfinding problem, concerning planning the best paths for the simultaneously moving agents in the crowded environment with obstacles. The proposed approach is based on the two-stage approach. In the first stage, a navigation mesh for passable regions in rectangular 2D environment is created using Quad-trees algorithm. In the second stage, a path is found for each agent present in environment using Dijkstra or A* algorithm. To find efficient paths in crowded environment, density information for each passable region is stored. Density information is further mapped on graph edges along with the distance values. The key point is that the moving agents reevaluate their paths accordingly to the re-planning strategy. Three strategies are considered: (i) periodical re-planning, (ii) periodical with initial re-planning, and (iii) the proposed way called event-driven re-planning. The created and implemented experimentation system can be adopted by the practical user for testing the twostage combinations of algorithms. The results of investigations, based on simulation experiments made with this system, presented in the paper, showed that the proposed approach is promising. [ABSTRACT FROM AUTHOR]
Copyright of Journal of Intelligent & Fuzzy Systems is the property of Sage Publications Inc. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Links:
  – Type: pdflink
Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 121054438
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: Multi-agent pathfinding in the crowded environment with obstacles: Algorithms and experimentation system.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Hudziak%2C+Mariusz%22">Hudziak, Mariusz</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Pozniak-Koszalka%2C+Iwona%22">Pozniak-Koszalka, Iwona</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Koszalka%2C+Leszek%22">Koszalka, Leszek</searchLink><relatesTo>1</relatesTo><i> leszek.koszalka@pwr.edu.pl</i><br /><searchLink fieldCode="AR" term="%22Kasprzak%2C+Andrzej%22">Kasprzak, Andrzej</searchLink><relatesTo>1</relatesTo>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Journal+of+Intelligent+%26+Fuzzy+Systems%22">Journal of Intelligent & Fuzzy Systems</searchLink>. 2017, Vol. 32 Issue 2, p1561-1573. 13p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Parallel+scheduling+%28Computer+scheduling%29%22">Parallel scheduling (Computer scheduling)</searchLink><br /><searchLink fieldCode="DE" term="%22Sequential+scheduling%22">Sequential scheduling</searchLink><br /><searchLink fieldCode="DE" term="%22Parallel+algorithms%22">Parallel algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Distributed+algorithms%22">Distributed algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithmic+randomness%22">Algorithmic randomness</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: The objective of this paper is to give a tool for the practical users, looking for the efficient way for solving pathfinding problem, concerning planning the best paths for the simultaneously moving agents in the crowded environment with obstacles. The proposed approach is based on the two-stage approach. In the first stage, a navigation mesh for passable regions in rectangular 2D environment is created using Quad-trees algorithm. In the second stage, a path is found for each agent present in environment using Dijkstra or A* algorithm. To find efficient paths in crowded environment, density information for each passable region is stored. Density information is further mapped on graph edges along with the distance values. The key point is that the moving agents reevaluate their paths accordingly to the re-planning strategy. Three strategies are considered: (i) periodical re-planning, (ii) periodical with initial re-planning, and (iii) the proposed way called event-driven re-planning. The created and implemented experimentation system can be adopted by the practical user for testing the twostage combinations of algorithms. The results of investigations, based on simulation experiments made with this system, presented in the paper, showed that the proposed approach is promising. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Journal of Intelligent & Fuzzy Systems is the property of Sage Publications Inc. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=121054438
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.3233/JIFS-169150
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 13
        StartPage: 1561
    Subjects:
      – SubjectFull: Parallel scheduling (Computer scheduling)
        Type: general
      – SubjectFull: Sequential scheduling
        Type: general
      – SubjectFull: Parallel algorithms
        Type: general
      – SubjectFull: Distributed algorithms
        Type: general
      – SubjectFull: Algorithmic randomness
        Type: general
    Titles:
      – TitleFull: Multi-agent pathfinding in the crowded environment with obstacles: Algorithms and experimentation system.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Hudziak, Mariusz
      – PersonEntity:
          Name:
            NameFull: Pozniak-Koszalka, Iwona
      – PersonEntity:
          Name:
            NameFull: Koszalka, Leszek
      – PersonEntity:
          Name:
            NameFull: Kasprzak, Andrzej
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 02
              Text: 2017
              Type: published
              Y: 2017
          Identifiers:
            – Type: issn-print
              Value: 10641246
          Numbering:
            – Type: volume
              Value: 32
            – Type: issue
              Value: 2
          Titles:
            – TitleFull: Journal of Intelligent & Fuzzy Systems
              Type: main
ResultId 1