‘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:
Scientists Discover That the Brain Responds to Others’ Actions as if They Were Its Own
When we watch someone move their finger, our brain doesn’t remain passive. Research conducted by scientists from HSE University and Lausanne University Hospital shows that observing movement activates the motor cortex as if we were performing the action ourselves—while simultaneously ‘silencing’ unnecessary muscles. The findings were published in Scientific Reports.
Russian Scientists Investigate Age-Related Differences in Brain Damage Volume Following Childhood Stroke
A team of Russian scientists and clinicians, including Sofya Kulikova from HSE University in Perm, compared the extent and characteristics of brain damage in children who experienced a stroke either within the first four weeks of life or before the age of two. The researchers found that the younger the child, the more extensive the brain damage—particularly in the frontal and parietal lobes, which are responsible for movement, language, and thinking. The study, published in Neuroscience and Behavioral Physiology, provides insights into how age can influence the nature and extent of brain lesions and lays the groundwork for developing personalised rehabilitation programmes for children who experience a stroke early in life.
Scientists Test Asymmetry Between Matter and Antimatter
An international team, including scientists from HSE University, has collected and analysed data from dozens of experiments on charm mixing—the process in which an unstable charm meson oscillates between its particle and antiparticle states. These oscillations were observed only four times per thousand decays, fully consistent with the predictions of the Standard Model. This indicates that no signs of new physics have yet been detected in these processes, and if unknown particles do exist, they are likely too heavy to be observed with current equipment. The paper has been published in Physical Review D.
HSE Scientists Reveal What Drives Public Trust in Science
Researchers at HSE ISSEK have analysed the level of trust in scientific knowledge in Russian society and the factors shaping attitudes and perceptions. It was found that trust in science depends more on everyday experience, social expectations, and the perceived promises of science than on objective knowledge. The article has been published in Universe of Russia.
Institute for Robotics Systems Established at HSE University
As decided by the HSE University Academic Council, a new Institute for Robotics Systems will be established at HSE, and with a strong fundamental base. It will cooperate with relevant departments across the university and engage students and doctoral candidates in research and development (R&D). First Vice Rector of HSE University and Director of the Institute for Statistical Studies and Economics of Knowledge, Leonid Gokhberg, discussed the expected practical results and the framework for cooperation with an industrial partner.
HSE Seeks New Ideas for AI Agents: Initiative Competition Launched
HSE University is inviting researchers and lecturers to present concepts for new digital products based on artificial intelligence. The best projects will receive expert and technological support. Applications are open until December 19, 2025.
IDLab: Fascinating Research, Tough Deadlines, and Academic Drive
The International Laboratory of Intangible-driven Economy (IDLab) was established at the HSE campus in Perm 11 years ago. Its expertise in data processing and analysis allows researchers to combine fundamental studies with applied projects, including the development of risk and cybersecurity models for Sber. The head of the laboratory, Professor Petr Parshakov, and Senior Research Fellow Professor Mariya Molodchik spoke to the HSE News Service about IDLab’s work.
HSE Lecturers Awarded Yandex ML Prize 2025
The Yandex ML Prize is awarded to lecturers and heads of educational programmes who contribute to the development of artificial intelligence in Russia. This year, 10 laureates were selected from 300 applicants, including three members of the HSE Faculty of Computer Science (FCS). A special Hall of Fame award was also presented for contributions to the establishment of machine learning as an academic field. One of the recipients was Dmitry Vetrov, Research Professor at the HSE FCS.
HSE Tops Ranking of Universities Participating in Priority 2030 Programme
The Russian Ministry of Science and Higher Education has published an updated list of participants in the Priority 2030 programme. A total of 106 universities will receive support this year. HSE University was included in the first group and topped the ranking.
HSE University and Banking and Finance Academy of Uzbekistan Sign Memorandum on Scientific Cooperation
The partnership aims to foster academic collaboration in the fields of global economics, sustainable development, and Islamic finance. Strengthening academic ties with Uzbekistan represents a promising direction for scientific exchanges and the implementation of international projects in sustainable development.