Sign In

Optimization of Edge Directions and Weights for Mixed Guidance Graphs in Lifelong Multi-Agent Path Finding

Created by
  • Haebom
Category
Empty

μ €μž

Yulun Zhang, Varun Bhatt, Matthew C. Fontaine, Stefanos Nikolaidis, Jiaoyang Li

πŸ’‘ κ°œμš”

λ³Έ 논문은 μ§€μ†μ μœΌλ‘œ μƒˆλ‘œμš΄ λͺ©ν‘œλ₯Ό λΆ€μ—¬λ°›λŠ” 평생 닀쀑 μ—μ΄μ „νŠΈ 경둜 μ°ΎκΈ°(Lifelong MAPF) λ¬Έμ œμ—μ„œ μ—μ΄μ „νŠΈμ˜ 이동을 효과적으둜 μ•ˆλ‚΄ν•˜κΈ° μœ„ν•œ ν˜Όν•© μ•ˆλ‚΄ κ·Έλž˜ν”„ μ΅œμ ν™”(Mixed Guidance Graph Optimization, MGGO) 방법을 μ œμ•ˆν•œλ‹€. 기쑴의 μ•ˆλ‚΄ κ·Έλž˜ν”„ μ΅œμ ν™”(GGO)λŠ” 에지 κ°€μ€‘μΉ˜λ§Œμ„ μ‚¬μš©ν•˜μ—¬ μ—μ΄μ „νŠΈμ—κ²Œ λΆ€λ“œλŸ¬μš΄ μ•ˆλ‚΄λ₯Ό μ œκ³΅ν–ˆμœΌλ‚˜, λ³Έ μ—°κ΅¬λŠ” 에지 λ°©ν–₯ μ΅œμ ν™”λ₯Ό μΆ”κ°€ν•˜μ—¬ 보닀 μ—„κ²©ν•œ μ•ˆλ‚΄λ₯Ό μ œκ³΅ν•œλ‹€. 두 가지 MGGO 방법과 ꡐ톡 νŒ¨ν„΄μ„ κ³ λ €ν•œ GGO 방법둠을 μ œμ‹œν•˜λ©°, μ œμ•ˆ 방법둠은 κΈ°μ‘΄ GGO보닀 μ—μ΄μ „νŠΈμ˜ 이동을 더 효율적으둜 ν†΅μ œν•  수 μžˆμŒμ„ μ‹œμ‚¬ν•œλ‹€.

πŸ”‘ μ‹œμ‚¬μ  및 ν•œκ³„

β€’
MGGOλŠ” 에지 κ°€μ€‘μΉ˜λΏλ§Œ μ•„λ‹ˆλΌ 에지 λ°©ν–₯κΉŒμ§€ μ΅œμ ν™”ν•¨μœΌλ‘œμ¨ LMAPFμ—μ„œ μ—μ΄μ „νŠΈμ˜ 경둜 μ•ˆλ‚΄λ₯Ό λ”μš± μ—„κ²©ν•˜κ³  효과적으둜 μ œμ–΄ν•  수 μžˆλ‹€.
β€’
ꡐ톡 νŒ¨ν„΄μ„ λ°˜μ˜ν•œ GGO 방법은 μ‹€μ œ ν™˜κ²½μ—μ„œ λ°œμƒν•  수 μžˆλŠ” μ—μ΄μ „νŠΈ κ°„μ˜ μƒν˜Έμž‘μš©μ„ κ³ λ €ν•˜μ—¬ λ”μš± μ‹€μš©μ μΈ μ•ˆλ‚΄ κ·Έλž˜ν”„λ₯Ό 생성할 수 μžˆλ‹€.
β€’
두 λ‹¨κ³„λ‘œ 에지 λ°©ν–₯κ³Ό κ°€μ€‘μΉ˜λ₯Ό 뢄리 μ΅œμ ν™”ν•˜λŠ” 방법은 계산 νš¨μœ¨μ„±μ΄ 높을 수 μžˆμ§€λ§Œ, 두 μš”μ†Œ κ°„μ˜ μƒν˜Έμž‘μš©μ„ μΆ©λΆ„νžˆ λ°˜μ˜ν•˜μ§€ λͺ»ν•  κ°€λŠ₯성이 μžˆλ‹€.
πŸ‘
Made with Slashpage