‘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 Have Modelled Supercapacitor Operation at Molecular and Ionic Level
HSE scientists used supercomputer simulations to study the behaviour of ions and water molecules inside the nanopores of a supercapacitor. The results showed that even a very small amount of water alters the charge distribution inside the nanopores and influences the device’s energy storage capacity. This approach makes it possible to predict how supercapacitors behave under different electrolyte compositions and humidity conditions. The paper has been published in Electrochimica Acta. The study was supported by a grant from the Russian Science Foundation (RSF).
Designing an Accurate Reading Skills Test: Why Parallel Texts are Important in Dyslexia Diagnosis
Researchers from the HSE Centre for Language and Brain have developed a tool for accurately assessing reading skills in adults with reading impairments. It can be used, for instance, before and after sessions with a language therapist. The tool includes two texts that differ in content but are equal in complexity: participants were observed to read them at the same speed, make a similar number of errors, and understand the content to the same degree. Such parallel texts will enable more accurate diagnosis of dyslexia and better monitoring of the effectiveness of interventions aimed at addressing it. The paper has been published in Educational Studies.
HSE University Launches Development of Domestic 6G Communication Technologies Based on Sub-Terahertz Microelectronics
HSE University has launched a large-scale research and engineering initiative to develop domestic technologies for next-generation 6G communication systems. The project is being carried out by the team of the Strategic Technological Project 'Trusted 6G Communication Systems Technology Suite' implemented under the Priority 2030 programme.
Intellectual Capital in the Face of Shocks: Russia and Iran Explore Internationalisation
In today's issue of Schola, Mariya Molodchik, Senior Research Fellow at the International Laboratory of Intangible-Driven Economy and Professor at the School of Economics and Finance at HSE University’s Campus in Perm, discusses a joint project with Iran University of Science and Technology, titled 'Internationalization of Companies from Developing Countries: The Role of Intellectual Resources in Response to Exogenous Shocks.'
HSE Researchers Introduce Novel Symmetry-Aware Neural Network Architecture
Researchers at the HSE Laboratory for Geometric Algebra and Applications have developed a new neural network architecture that can accelerate and streamline data analysis in physics, biology, and engineering. The scientists presented their solution on July 16 in Vancouver at ICML 2025, one of the world's leading conferences on machine learning. Both the paper and the source code are publicly available.
Students from HSE and Other Universities Carry Out Research Expedition at New Chersonesos
As part of the Rediscovering Russia student expedition programme, HSE University organised a research trip under the framework of the School for Young Humanities Scholars to the New Chersonesos museum and church complex in Sevastopol. The results of this expedition will form the basis for proposals on educational projects aimed at shaping young people’s historical memory of the role of Chersonesos, Crimea, and the Byzantine legacy in the history of Russian culture and statehood.
HSE Researchers Determine Frequency of Genetic Mutations in People with Pulmonary Hypertension
For the first time in Russia, a team of scientists and clinicians has conducted a large-scale genetic study of patients with pulmonary arterial hypertension. The team, which included researchers from the International Laboratory of Bioinformatics at the HSE Faculty of Computer Science, analysed the genomes of over a hundred patients and found that approximately one in ten carried pathogenic mutations in the BMPR2 gene, which is responsible for vascular growth. Three of these mutations were described for the first time. The study has been published in Respiratory Research.
First Caucasus School on Experimental Research and Cognitive Sciences Takes Places in Adygea
On September 17–20, 2025, the First Caucasus School on Experimental Research and Cognitive Sciences took place at the Gornaya Legenda venue of Adyghe State University (ASU). The event was organised by the ASU Experimental Linguistics Laboratory, the HSE Centre for Language and Brain, and the HSE Centre for Sociocultural and Ethnolinguistic Studies. The school brought together over 50 participants—students, doctoral candidates, and early-career researchers from across Russia, along with lecturers and speakers from France, Serbia, China, Turkey, Kazakhstan, and Uzbekistan.
HSE Scientists Reveal How Disrupted Brain Connectivity Affects Cognitive and Social Behaviour in Children with Autism
An international team of scientists, including researchers from the HSE Centre for Language and Brain, has for the first time studied the connectivity between the brain's sensorimotor and cognitive control networks in children with autism. Using fMRI data, the researchers found that connections within the cognitive control network (responsible for attention and inhibitory control) are weakened, while connections between this network and the sensorimotor network (responsible for movement and sensory processing) are, by contrast, excessively strong. These features manifest as difficulties in social interaction and behavioural regulation in children. The study has been published in Brain Imaging and Behavior.
‘The Future Is Not Predetermined—We Shape It with the Decisions We Make Today’
The strategic technological project ‘National Centre of Science, Technology, and Socio-Economic Foresight’ at HSE University spans horizons of 10 to 30 years and involves developing new methodologies of scenario analysis. It brings together researchers from different fields and helps to form a holistic vision of the future. The aim of the project is not only to produce forecasts but also to generate practical recommendations for government and business. Anastasia Likhacheva, Dean of the HSE Faculty of World Economy and International Affairs, explains why it is important to learn to ask the right questions about the future.