‘Our Result Was Recognised Not Only Within the Project Defence but Also on International Scale’
This year, the European AI Conference (ECAI 2025) accepted an article titled ‘Multi-Agent Path Finding for Large Agents is Intractable’ by Artem Agafonov, a second-year student of the Applied Mathematics and Information Science Bachelor’s programme at HSE University’s Faculty of Computer Science. The work was co-authored by Konstantin Yakovlev, Head of the Joint Department with Intelligent Technologies of System Analysis and Management at the Federal Research Centre ‘Informatics and Management’ of the RAS and Associate Professor at the Faculty of Applied Sciences. In the interview, Artem Agafonov explained how he came up with the idea for the article and how he was able to present it at an A-level conference.
How It Began
At the beginning of my second year, I needed to choose a course project for the year. One topic that caught my attention was ‘Multi-Agent Trajectory Planning’ proposed by Konstantin Yakovlev. After reading the description of the project, I realised that it would allow me to put my knowledge of algorithms into practice and gain new research experience. Additionally, I considered the potential for significant results within the bounds of this project to be an important factor in my decision.

I started working on the project by reviewing the existing research in the field of multi-agent pathfinding (MAPF), for which I had read many scientific articles. After a month, Prof. Yakovlev gave me several relevant problems. One of them was to create a polynomial algorithm for solving a MAPF problem with a large number of agents. He warned me that he had already offered this problem to other graduate students and researchers, but none of them had been able to solve it. Although this was a daunting comment, I decided to give it a try.
What the Problem Was
In simple terms, the problem can be described as follows. In a MAPF problem, we have a graph with a set of vertices connected by edges—and a set of agents that are located at these vertices. Each agent has a target vertex that it wants to reach by moving along the edges. We need to find a way for all agents to reach their targets without any conflicts, which means that two agents should never end up in the same vertex. It is necessary either to define a transition plan, moving along which agents will be able to reach their target vertices, or confirm that it is impossible to build such a plan.
LA-MAPF (Large Agents MAPF) is an extension of the previous MAPF problem. In this case, the graph can be located in 2D or 3D space, and each agent has its own geometric shape, such as a circle in a simple case. Now, conflicts can happen not only when two agents end up in the same vertex, but also when their geometric shapes intersect during movement in space.
A polynomial algorithm for solving the MAPF problem exists and is called Push-and-Rotate. However, there is no such algorithm for LA-MAPF. Therefore, the development of such an algorithm was a relevant question. One feature of polynomial algorithms is that their running time increases more slowly with the size of input data compared to non-polynomial algorithms. This makes them interesting not only theoretically, but also practically.
The Way It Is
At first, I attempted to come up with an appropriate algorithm. To do this, I created programmes to generate a test task, solve it using a complete search, and visualise the movement of agents within it. I proposed various hypotheses and tested them using these programmes, but each time, the programme failed to perform on some test cases. The challenges led me to conclusion that it was not possible to solve the problem in polynomial time. This seemed to explain why other researchers were unable to solve the issue. Therefore, I decided to attempt to prove it.
Here, the knowledge I gained about the complexity theory of algorithms and how to prove NP-hard problems in the course ‘Algorithms and Data Structures’ has been very useful to me. After initial success came relatively quickly, it took several months of intense work, phone calls, and discussions to simplify the proof and ensure its accuracy. As a result, we have concluded that the LA-MAPP problem is indeed NP-hard, meaning that there is no deterministic polynomial-time algorithm for solving it if the complexity classes P and NP are unequal (this assumption is one of the Millennium Prize Problems).
The Result Is Worth an Article
Prof. Yakovlev stated that the result was significant, and we decided not only to present it at the course project defenсe (it earned ten points), but also to share it with the broader scientific community by publishing an article. We chose the ECAI conference as it is one of the most prestigious conferences. HSE University’s Scientometrics Centre, for example, has included it in its ACONF list, and the application deadline in early May was convenient for us. We invested a lot of time and effort into making the article clear and useful for readers, so we were delighted to receive approval for publication in early July.
The article follows a standard structure: introduction, literature review, problem statement, proof, discussion on the significance of the result, and directions for future work. Some sections were adapted from the original course paper and translated into English, while most of the content was created specifically for the article.
The main difficulty was not in writing the article, but rather in achieving a satisfactory final result. It was a bit daunting as time was running out before the defence of the course project, and no significant progress had been made. Therefore, when I formulated my first version proving that it was impossible to solve the problem, I felt relieved to make such a discovery, as it took the pressure off me regarding the lack of progress on the course paper.
Overall, I am satisfied with my work. Although I did not initially expect to achieve anything significant in this area, it is gratifying that our result was recognised not only within the project defence but also on a serious international scale. It is wonderful that the knowledge I gained during my university studies has been put to use in my work. I’m glad I enrolled in Applied Mathematics and Information Science, as the learning experience was both interesting and beneficial.
See also:
Updated Facts and Figures and Dashboards Now Available on HSE Website
The HSE Office of Analytics and Data Management, together with the Visual Communications Unit, has developed a new Facts and Figures about HSE University page on the HSE website. In addition, all university staff now have access to a dashboard with the updated indicators of the Priority 2030 programme.
Immune System Error: How Antibodies in Multiple Sclerosis Mistake Their Targets
Researchers at HSE University and the Institute of Bioorganic Chemistry of the Russian Academy of Sciences (IBCh RAS) have studied how the immune system functions in multiple sclerosis (MS), a disease in which the body's own antibodies attack its nerve fibres. By comparing blood samples from MS patients and healthy individuals, scientists have discovered that the immune system in MS patients can mistake viral proteins for those of nerve cells. Several key proteins have also been identified that could serve as new biomarkers for the disease and aid in its diagnosis. The study has been published in Frontiers in Immunology. The research was conducted with support from the Russian Science Foundation.
HSE to Entrust Routine CPD Programme Development to AI
HSE University, together with the EdTech company CDO Global, is launching AI-based constructors to streamline the design of continuing professional development (CPD) courses. The new service will automate the preparation of teaching materials and assessment tools, significantly reducing the time and resources required of lecturers and instructional designers.
‘Territory of the Future. Moscow 2030’ Forum-Festival to Feature Innovative Projects from HSE Graduates
Until September 14, 2025, the Russian capital is hosting a large-scale forum-festival called ‘Territory of the Future: Moscow 2030’ —a space for technology, science, and innovation. This event showcases cutting-edge developments in medicine, astronautics, and the digital economy. HSE Art and Design School is participating in the festival with two graduate projects in Product and Industrial Design.
‘The Goal of Modern Geography Is To Digitise Expert Knowledge and Integrate It with Big Data’
The importance of geographical science is increasing, as is the demand for education in this field. Since 2020, application numbers for Bachelor’s programmes at HSE University’s Faculty of Geography and Geoinformation Technology have climbed by 30%, while interest in Master’s programmes has also expanded, with applications up 10–15%. Nikolay Kurichev, Dean of the Faculty, spoke about this at a press conference hosted by MIA Rossiya Segodnya.
HSE Shares Its Experience of Urban Strategies at International Summer School in China
In the context of intensifying global geopolitical and technological competition, leading Chinese educational institutions—Zhejiang International Studies University and Peking University—organised an International Summer School. Their joint programme focused on studying global, regional, and urban development strategies. The HSE Faculty of Urban and Regional Development took part in this event.
Scientists Develop Effective Microlasers as Small as a Speck of Dust
Researchers at HSE University–St Petersburg have discovered a way to create effective microlasers with diameters as small as 5 to 8 micrometres. They operate at room temperature, require no cooling, and can be integrated into microchips. The scientists relied on the whispering gallery effect to trap light and used buffer layers to reduce energy leakage and stress. This approach holds promise for integrating lasers into microchips, sensors, and quantum technologies. The study has been published in Technical Physics Letters.
HSE Scientists Test New Method to Investigate Mechanisms of New Word Acquisition
Researchers at the HSE Centre for Language and Brain were among the first to use transcranial alternating current stimulation to investigate whether it can influence the acquisition of new words. Although the authors of the experiment have not yet found a link between brain stimulation and word acquisition, they believe that adjusting the stimulation parameters may yield different results in the future. The study has been published in Language, Cognition and Neuroscience.
Twenty vs Ten: HSE Researcher Examines Origins of Numeral System in Lezgic Languages
It is commonly believed that the Lezgic languages spoken in Dagestan and Azerbaijan originally used a vigesimal numeral system, with the decimal system emerging later. However, a recent analysis of numerals in various dialects, conducted by linguist Maksim Melenchenko from HSE University, suggests that the opposite may be true: the decimal system was used originally, with the vigesimal system developing later. The study has been published in Folia Linguistica.
HSE University–St Petersburg and Universiti Teknologi Malaysia Release First Book of Mirror Laboratory
Malaysia hosted the AHIBS 'Weaving Horizons for Sustainable Impact' international conference, which featured the presentation of the first Russian–Malaysian book of research articles.