• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • A
  • A
  • A
  • A
  • A
Обычная версия сайта
  • RU
  • EN
  • HSE University
  • Publications
  • Book chapter
  • Any-Angle Pathfinding for Multiple Agents Based on SIPP Algorithm
  • RU
  • EN
Расширенный поиск
Высшая школа экономики
Национальный исследовательский университет
Priority areas
  • business informatics
  • economics
  • engineering science
  • humanitarian
  • IT and mathematics
  • law
  • management
  • mathematics
  • sociology
  • state and public administration
by year
  • 2027
  • 2026
  • 2025
  • 2024
  • 2023
  • 2022
  • 2021
  • 2020
  • 2019
  • 2018
  • 2017
  • 2016
  • 2015
  • 2014
  • 2013
  • 2012
  • 2011
  • 2010
  • 2009
  • 2008
  • 2007
  • 2006
  • 2005
  • 2004
  • 2003
  • 2002
  • 2001
  • 2000
  • 1999
  • 1998
  • 1997
  • 1996
  • 1995
  • 1994
  • 1993
  • 1992
  • 1991
  • 1990
  • 1989
  • 1988
  • 1987
  • 1986
  • 1985
  • 1984
  • 1983
  • 1982
  • 1981
  • 1980
  • 1979
  • 1978
  • 1977
  • 1976
  • 1975
  • 1974
  • 1973
  • 1972
  • 1971
  • 1970
  • 1969
  • 1968
  • 1967
  • 1966
  • 1965
  • 1964
  • 1963
  • 1958
  • More
Subject
News
July 15, 2026
Economists Propose More Effective Approach to Reducing Smoking
Economists at HSE University have examined how smokers respond to changes in cigarette prices. When tobacco prices increase, cigarette consumption does not always decline. In fact, spending on tobacco may even rise: according to the researchers, a 1% decrease in cigarette affordability leads to a 0.28% increase in per capita tobacco expenditure. The findings suggest that to reduce smoking rates, tobacco prices must rise faster than household incomes. The study has been published in Voprosy Statistiki.
July 15, 2026
HSE MIEM Students to Develop Two Satellites from Scratch for Orbital Experiments
The devices, created by student teams, will conduct space research on the properties of promising solar cells, on-board energy storage systems, and serial electronics for student satellites.
July 13, 2026
Biologists Discover Unique Properties of MiR-93-5p MicroRNA in Prostate Cancer
Researchers at the International Laboratory of Microphysiological Systems of the HSE Faculty of Biology and Biotechnology investigated how different isoforms of the same microRNA influence gene function in prostate adenocarcinoma. The study found that in some cases, microRNAs can reinforce each other’s effects by targeting and suppressing the same genes. This finding offers a fresh perspective on the molecular mechanisms underlying tumour development and on the search for disease biomarkers. The results have been published in PeerJ.

 

Have you spotted a typo?
Highlight it, click Ctrl+Enter and send us a message. Thank you for your help!

Publications
  • Books
  • Articles
  • Chapters of books
  • Working papers
  • Report a publication
  • Research at HSE

?

Any-Angle Pathfinding for Multiple Agents Based on SIPP Algorithm

P. 586–593.
Yakovlev K., Andreychuk A.

The problem of finding conflict-free trajectories for multiple agents of identical circular shape, operating in shared 2D workspace, is addressed in the paper and decoupled, e.g., prioritized, approach is used to solve this problem. Agents’ workspace is tessellated into the square grid on which any-angle moves are allowed, e.g. each agent can move into an arbitrary direction as long as this move follows the straight line segment whose endpoints are tied to the distinct grid elements. A novel any-angle planner based on Safe Interval Path Planning (SIPP) algorithm is proposed to find trajectories for an agent moving amidst dynamic obstacles (other agents) on a grid. This algorithm is then used as part of a prioritized multi-agent planner AA-SIPP(m). On the theoretical side, we show that AA-SIPP(m) is complete under well-defined conditions. On the experimental side, in simulation tests with up to 200 agents involved, we show that our planner finds much better solutions in terms of cost (up to 20%) compared to the planners relying on cardinal moves only

Language: English
Full text
Text on another site
Keywords: path planningPath findingmulti-agent path findingSIPPany-angle

In book

Proceedings of the 27th International Conference on Automated Planning and Scheduling (ICAPS 2017)
Palo Alto: AAAI Press, 2017.
Similar publications
Coverage of Agricultural Areas by a Group of Unmanned Aerial Vehicles Considering Wind Load and Energy Consumption Constraints
Faizullin R., Mustafin M., Svinin M. et al., , in: 2025 9th International Conference on Information, Control, and Communication Technologies (ICCT-2025).: IEEE, 2025. P. 1–4.
This work addresses the problem of energy-constrained coverage of agricultural fields using a fleet of identical unmanned aerial vehicles (UAVs). Each UAV must complete a spraying mission over a designated area, subject to limited battery capacity. To ensure energy feasibility, static charging stations are deployed along the field’s perimeter. The agricultural field is first partitioned ...
Added: June 23, 2026
Implementation of Rev1 and Rev2 Bug Family Algorithms in ROS Noetic
Roslavtsev M., Eryomin A., Safin R. et al., , in: 2024 8th International Conference on Information, Control, and Communication Technologies (ICCT).: IEEE, 2024. P. 1–5.
Modern map-dependent algorithms for mobile robot navigation typically overload a CPU and memory with a gradually increasing amount of environmental data. In contrast, Bug family local path planning algorithms operate without mapping and have significantly lower hardware requirements. Bug algorithms use real-time measurements from visual and touch sensors to make immediate decisions on direction of ...
Added: November 25, 2025
ROS-based navigation in unknown environment using the InsertBug algorithm: Issues of practical usage
Nekerov I., Safin R., Tsoy T. et al., Ученые записки Казанского университета. Серия: Физико-математические науки 2025 Vol. 167 No. 1 P. 38–53
BUG algorithms are effective strategies for local path planning in unknown environments. This article presents a practical implementation of the InsertBug algorithm using the Robot Operating System (ROS) and highlights its challenges. The algorithm relies on laser sensor and odometry data to construct a locally optimal path in an unknown terrain. Its evaluation was performed ...
Added: November 25, 2025
Implementation and Validation of the CautiousBug Algorithm in ROS Noetic
Roman M., Eryomin A., Tsoy T. et al., , in: 2024 8th International Conference on Information, Control, and Communication Technologies (ICCT).: IEEE, 2024. Ch. 51 P. 1–4.
In this paper, we present an implementation of the CautiousBug algorithm within the Noetic distribution of the Robot Operating System (ROS). Bug algorithms address a challenge of robot navigation in unknown environments without relying on pre-existing maps or constructing new ones. These algorithms utilize odometry data, operate without a map, require minimal computational resources, and can ...
Added: May 28, 2025
ROS-based navigation in unknown environment with TangentBug Algorithm: issues of practical usage
Gorokhov L., Safin R., Magid E., , in: Proceedings Volume 13404, Fifth International Conference on Control, Robotics, and Intelligent System (CCRIS 2024).: SPIE, 2024. Ch. 134040X.
Path planning Bug algorithms play a crucial role in addressing the problem of navigating through unknown environments. This paper presents a practical implementation of the TangentBug algorithm within the Robot Operating System along with a discussion of encountered issues of practical usage. The TangentBug algorithm uses data from laser and odometry sensors to construct locally optimal paths without ...
Added: February 19, 2025
Implementation of Bug1 and Bug2 Basic Path-Planning Algorithms for a TurtleBot 3 Robot in ROS Noetic
Spektor I., Zagirov A., Safin R. et al., , in: Proceedings Of The 2024 International Conference On Artificial Life And Robotics February 22 To 25, 2024 J:Com Horutohall, Oita, Japan. 29Th Arob International Meeting Series.: ALife Robotics Corporation Ltd., 2024. P. 272–275.
Added: February 19, 2025
Decentralized Unlabeled Multi-agent Pathfinding Via Target And Priority Swapping
Dergachev S., Yakovlev K., , in: ECAI 2024. 27th European Conference on Artificial Intelligence, October 19 – 24 October 2024, Santiago de Compostela, Spain – Including 13th Conference on Prestigious Applications of Intelligent Systems (PAIS 2024).: IOS Press, 2024. P. 4344–4351.
Added: September 11, 2024
Decentralized Unlabeled Multi-agent Navigation in Continuous Space
Dergachev S., Yakovlev K., , in: Interactive Collaborative Robotics. 9th International Conference, ICR 2024, Mexico City, Mexico, October 14–18, 2024, Proceedings.: Cham: Springer, 2024. P. 186–200.
Added: September 11, 2024
2.5D Mapping, Pathfinding and Path Following For Navigation Of A Differential Drive Robot In Uneven Terrain
Dergachev S., Yakovlev K., Муравьев К. Ф., , in: IFAC-PapersOnLineVol. 55. Issue 38: 13th IFAC Symposium on Robot Control SYROCO 2022.: Elsevier, 2022. P. 80–85.
Safe navigation in uneven terrains is an important problem in robotic research. In this paper we propose a 2.5D navigation system which consists of elevation map building, path planning and local path following with obstacle avoidance. For local path following we use Model Predictive Path Integral (MPPI) control method. We propose novel cost-functions for MPPI ...
Added: September 8, 2023
Towards a Complete Multi-agent Pathfinding Algorithm for Large Agents
Dergachev S., Yakovlev K., , in: Advances in Computational Intelligence. 21st Mexican International Conference on Artificial Intelligence, MICAI 2022, Monterrey, Mexico, October 24–29, 2022, Proceedings* 1.: Cham: Springer, 2022. P. 355–367.
Multi-agent pathfinding (MAPF) is a challenging problem which is hard to solve optimally even when simplifying assumptions are adopted, e.g. planar graphs (typically – grids), discretized time, uniform duration of move and wait actions etc. On the other hand, MAPF under such restrictive assumptions (also known as the Classical MAPF) is equivalent to the so-called ...
Added: May 16, 2023
Modified E3 exploration algorithm for unknown environments with obstacles
Mavrin I., Tsoy T., Magid E., , in: 2022 13th Asian Control Conference (ASCC).: IEEE, 2022. P. 1413–1418.
An efficient autonomous exploration of an unknown environment is an important task for mobile robots, which is required in many domains. This paper considers three existing exploration approaches: frontier exploration algorithm (FEA), greedy algorithm (GrA) and Ergodic Environmental Exploration algorithm (E3). While original E3 deals only with empty environments, we propose a new modified version ...
Added: October 28, 2022
Multi-agent Pathfinding With Continuous Time
Andreychuk A., Yakovlev K., Surynek P. et al., Artificial Intelligence 2022 Vol. 305 Article 103662
Multi-Agent Pathfinding (MAPF) is the problem of finding paths for multiple agents such that each agent reaches its goal and the agents do not collide. In recent years, variants of MAPF have risen in a wide range of real-world applications such as warehouse management and autonomous vehicles. Optimizing common MAPF objectives, such as minimizing sum-of-costs ...
Added: August 26, 2022
Разработка и имплементация сплайн-алгоритма планирования пути в среде ROS/Gazebo
Лавренов Р. О., Magid E., Мацуно Ф. et al., Информатика и автоматизация (Труды СПИИРАН) 2019 Т. 18 № 1 С. 57–84
Path planning for autonomous mobile robots is an important task within robotics field. It is common to use one of the two classical approaches in path planning: a global approach when an entire map of a working environment is available for a robot or local methods, which require the robot to detect obstacles with a ...
Added: November 9, 2021
Improving Continuous-time Conflict Based Search
Andreychuk A., Yakovlev K., Boyarski E. et al., , in: The Thirty-Fifth AAAI Conference on Artificial Intelligence. Technical Tracks 13Vol. 35.: AAAI Press, 2021. P. 11220–11227.
Conflict-Based Search (CBS) is a powerful algorithmic framework for optimally solving classical multi-agent path finding (MAPF) problems, where time is discretized into the time steps. Continuous-time CBS (CCBS) is a recently proposed version of CBS that guarantees optimal solutions without the need to discretize time. However, the scalability of CCBS is limited because it does ...
Added: October 21, 2021
Prioritizing Tasks Within a Robotic Transportation System for a Smart Hospital Environment
Safin R., Lavrenov R., Tsoy T. et al., , in: Interactive Collaborative Robotics: 6th International Conference, ICR 2021, St. Petersburg, Russia, September 27–30, 2021, Proceedings.: Springer, 2021. Ch. 16 P. 182–193.
This paper describes a design and an implementation of a small-scale robotic transportation system, which operates in a smart hospital environment. Within a proposed framework unmanned ground vehicles (UGV) perform transportation tasks between multiple stations that are located in different rooms. The UGVs navigate in the environment with moving objects in accordance with basic traffic ...
Added: October 21, 2021
Flatland Competition 2020: MAPF and MARL for Efficient Train Coordination on a Grid World
Laurent F., Schneider M., Scheller C. et al., , in: Proceedings of Machine Learning ResearchVol. 133: Proceedings of the NeurIPS 2020: Competition and Demonstration Track.: PMLR, 2021. P. 275–301.
The Flatland competition aimed at finding novel approaches to solve the vehicle re-scheduling problem (VRSP). The VRSP is concerned with scheduling trips in traffic networks and the re-scheduling of vehicles when disruptions occur, for example the breakdown of a vehicle. While solving the VRSP in various settings has been an active area in operations research ...
Added: September 6, 2021
Revisiting Bounded-Suboptimal Safe Interval Path Planning
Yakovlev K., Andreychuk A., Stern R., , in: Proceedings of the 30th International Conference on Automated Planning and Scheduling (ICAPS 2020).: AAAI Press, 2020. P. 300–304.
Added: October 21, 2020
GAN Path Finder: Preliminary results
Soboleva Natalia, Yakovlev K., , in: Proceedings of the 42nd German Conference on Artificial Intelligence (KI 2019), Kassel, Germany, September 23-26, 2019.: Springer, 2019. P. 316–324.
2D path planning in static environment is a well-known problem and one of the common ways to solve it is to (1) represent the environment as a grid and (2) perform a heuristic search for a path on it. At the same time 2D grid resembles much a digital image, thus an appealing idea comes ...
Added: February 3, 2020
  • About
  • About
  • Key Figures & Facts
  • Sustainability at HSE University
  • Faculties & Departments
  • International Partnerships
  • Faculty & Staff
  • HSE Buildings
  • HSE University for Persons with Disabilities
  • Public Enquiries
  • Studies
  • Admissions
  • Programme Catalogue
  • Undergraduate
  • Graduate
  • Exchange Programmes
  • Summer University
  • Summer Schools
  • Semester in Moscow
  • Business Internship
  • Research
  • International Laboratories
  • Research Centres
  • Research Projects
  • Monitoring Studies
  • Conferences & Seminars
  • Academic Jobs
  • Yasin (April) International Academic Conference on Economic and Social Development
  • Media & Resources
  • Publications by staff
  • HSE Journals
  • Publishing House
  • iq.hse.ru: commentary by HSE experts
  • Library
  • Economic & Social Data Archive
  • Video
  • HSE Repository of Socio-Economic Information
  • HSE1993–2026
  • Contacts
  • Copyright
  • Privacy Policy
  • Site Map
Edit