‘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:
‘Hedgehog’ Versus ‘Relatives’: Researchers Measure How the Brain Responds to Unexpected Words During Natural Speech
Russian neurophysiologists, including researchers from HSE University, have demonstrated the feasibility of using event-related fields (ERFs) to study brain activity during natural speech perception. The researchers showed that this approach can be applied not only to individual words but also to continuous speech. Their findings indicate that words whose meanings differ significantly from the preceding context require longer processing times. The study also reveals that the brain processes function words in two stages: first, it identifies their grammatical role and then uses this information to predict the next word. The study has been published in Frontiers in Human Neuroscience.
Four HSE Mathematics Graduates Win Russia’s Young Mathematicians Award
The winners of the Young Mathematicians of Russia Award were announced at the 6th Conference of Russia’s Mathematical Centres, held in Kazan in late August 2026. Four of the nine award recipients are graduates of the HSE Faculty of Mathematics: Associate Professor Alexander Kalmynin, PhD students Alexander Zaitsev and Petr Kucheryavyy, and researcher Dmitry Pirozhkov.
Hybrid Intelligence: Competencies in the Age of AI Discussed at Technoprom-2026
Artificial intelligence is not creating new professions, but rather transforming the nature of existing ones. This was the conclusion reached by participants in the panel session ‘Hybrid Intelligence: Digital and Human Drivers of Development,’ organised by the Institute for Statistical Studies and Economics of Knowledge (ISSEK) at HSE University as part of the 13th International Forum of Technological Development (Technoprom-2026). The experts discussed how the nature of work is changing, which skills are becoming increasingly sought after, and what prevents companies from fully capitalising on new technologies.
Scientists Develop New Solution for 6G Communication Systems
A terahertz neuromorphic circuit developed by scientists at HSE University could make 6G communication systems both more accurate and energy-efficient. The circuit enables indoor tracking of mobile devices with an accuracy of up to 99%. The results were presented at PIERS 2026, an international symposium on Photonics and Electromagnetism held in China.
Researchers Develop Method for Direct Generation of Regulatory DNA
Researchers at HSE University have developed a model for generating promoters and enhancers—DNA sequences that regulate gene activity. The model works directly with DNA nucleotides, without first transforming them into a continuous numerical representation. This solution could be useful for applications in synthetic biology and gene therapy. The study results were presented at the ICLR 2026 Workshop ‘Generative AI in Genomics (Gen^2): Barriers and Frontiers.’
Researchers at HSE University and Sber Train Neural Networks to Better Predict User Preferences
The HSE FCS AI and Digital Science Institute and Sber have introduced a new architecture for recommendation systems that combines two classes of models, enabling algorithms to better predict users’ interests and needs. A preprint of the paper has been published on arxiv.org and presented at Urban ML.
HSE Graduate School of Business and Alfa-Bank Hold Summer School for Students from China
Twenty-seven students from Chinese universities took part in the international summer school ‘Digital Product Management’ organised by the HSE Graduate School of Business and Alfa-Bank. Over the course of a week, participants explored the Russian economy and business environment, learned about current technology trends, and worked through the key stages of digital product development step by step—from researching user needs and defining a problem to developing a prototype and presenting their final project.
HSE Students Win Six Gold Medals at International Mathematics Competition for University Students
Students from the HSE Faculty of Computer Science (FCS) and Faculty of Mathematics have won six gold medals at the International Mathematics Competition for University Students (IMC). HSE students also received silver and bronze medals. One of the world’s most prestigious international university mathematics competitions, IMC 2026 was held in July–August this year in Blagoevgrad, Bulgaria.
Physicists Discover What Happens Inside a Stable Vortex
Large vortices with characteristic spiral arms are often observed in the atmosphere and the ocean. Physicists from HSE University have explained how these structures form and why they retain their shape. The researchers found that velocities at points located along the same vortex arc remain correlated even over long distances. At the same time, this correlation weakens rapidly with increasing distance from the vortex centre. These differences help explain the formation of spiral arms and may improve models of atmospheric and oceanic currents. The findings have been published in Physical Review Fluids.
HSE Computer Science Researchers Win Gold Medal at International Machine Learning Competition
A team comprising HSE International Laboratory of Statistical and Computational Genomics researchers Aleksei Shmelev and Nikita Chervov, 2025 graduate of the HSE Faculty of Computer Science’s Master’s programme in Data Analysis in Biology and Medicine Ivan Gevorkov, and two students from the United States achieved an outstanding result at the 2026 NeuroGolf international machine learning championship. The team won a gold medal and placed seventh overall.