‘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:
HSE Economists Reveal How the Wage Gap Emerges Among Vocational School Graduates
HSE researchers examined the careers of 600,000 graduates of Russian secondary vocational education programmes and found that at the start of their careers, the gender wage gap reaches 23%, doubling after three years. This disparity is largely due to male and female students choosing different occupations when enrolling in vocational schools. These were the findings made by Sergey Roshchin, Natalya Yemelina, and Ksenia Rozhkova from of the HSE Faculty of Economic Sciences. The article has been published in Educational Studies.
HSE Researchers Make Aldehydes Perform Dual Function
Chemists from HSE University have discovered a way to carry out a reductive addition reaction without using an external reducing agent. Instead, the required 'resource' is supplied by the aldehyde itself, one of the reaction participants. This approach helps prevent unwanted side reactions, reduces toxicity, and simplifies the production and synthesis of organic molecules, including those used in the manufacture of medicines. The study has been published in Journal of Catalysis.
Education in a Changing World: Russian–Chinese Dialogue in Beijing
How are universities, vocational education systems, and researcher training programmes evolving in response to new challenges? These questions were at the heart of the international forum ‘Reconfiguring Education in a Changing World: Russia–China Dialogues on Higher Education, Skills, and Research Training’, held in China in mid-June. The event was jointly organised by the HSE Institute of Education and the Graduate School of Education of Peking University, which hosted the forum on its campus.
Tabular Data Anonymisation Solution for Safe Use in AI Systems Developed at HSE University
The AI and Digital Science Institute at the HSE Faculty of Computer Science has developed a tabular data anonymisation service designed to prepare corporate datasets for use in analytics and AI applications. The solution can identify personal data in structured datasets, apply consistent and reproducible anonymisation rules, and generate the artifacts required for quality control, auditing, and subsequent use of data in secure environments.
HSE University and Unicamp Develop Partnership Projects
At the end of May, HSE University in Moscow received a delegation from the State University of Campinas (Unicamp, Brazil), which has held a strong, long-standing partnership with HSE. The meeting in Moscow took place as part of the International Partner Week, which was held from May 19 to 22 by HSE University–St Petersburg. The event was attended by Unicamp representatives: Rafael Dias, Director of International Affairs, and Milena Serafim, Associate Director of the Faculty of Applied Sciences.
HSE in Minsk: Developing Cooperation with Belarus
On May 26–29, 2026, an HSE University team visited Minsk, the capital of Belarus. The purpose of the trip was to meet and hold talks with Belarusian universities and scientific organisations—HSE University's current and prospective partners.
HSE Scientists Develop Method to Compress Large Language Models Without Losing Quality
Researchers from the AI and Digital Science Institute at the HSE Faculty of Computer Science have developed a new compression method for large language models such as GPT and LLaMA that reduces their size by 25–36% without additional training or significant loss of accuracy. This is the first approach to use mathematical transformations—specifically, rotations of model weights—to make models more amenable to compression with structured matrices. The study results have been published in ACL Findings 2025. The code is available on GitHub.
Machine Learning Models Can Help Reduce Volatility and Boost Stock Market Returns
The use of machine learning models makes it possible to achieve greater accuracy in predicting risks in the Russian stock market compared to classical econometric approaches. The predictive power of these models increases by 23%, while the average investor’s return can reach up to 13% per annum. These conclusions were drawn by Nikita Lysenok from the Department of Financial Market Infrastructure at the HSE Faculty of Economic Sciences. The paper has been published in Fundamental and Applied Mathematics.
HSE University at IRES 2026: Student Recruitment, Space Projects, and New Partnerships with India
The second Indo-Russian Education Summit (IRES 2026) took place in New Delhi on May 28–29. This year, the event brought together more than 70 leading Russian and Indian universities. Representatives from HSE University’s Moscow and St Petersburg campuses introduced prospective students to the university’s educational opportunities at the exhibition and shared their experience in developing Russian–Indian academic cooperation.
HSE Study Reveals Imbalance in the Generative AI Market
Researchers at HSE University analysed how effectively the global generative artificial intelligence market converts investment into real revenue, concluding that AI is currently developing faster than it is paying off. The results have been published in the journal Foresight and STI Governance.