‘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 Biologists Identify Factors That Accelerate Breast Cancer Recurrence
Scientists at HSE University have identified a molecular mechanism underlying aggressive breast cancer. They found that the signals supporting tumour growth originate not from the tumour itself but from its microenvironment. The researchers also demonstrated that reduced levels of the IGFBP6 protein in the tumour microenvironment lead to the accumulation of macrophages—immune cells associated with a higher risk of cancer recurrence. These findings already make it possible to assess patient risk more accurately and may, in the future, enable the development of drugs that target cells of the tumour microenvironment. The study has been published in Current Drug Therapy.
HSE’s CardioLife Test Among Winners of Data Fusion Awards 2026
The CardioLife genetic test—a development by the Centre for Biomedical Research and Technologies of the AI and Digital Science Institute at HSE University’s Faculty of Computer Science—has won the All-Russian cross-industry Data Fusion Awards, which recognise achievements in data and AI technologies. The project took first place in the Science–Business Partnership category, demonstrating a successful model for transferring technology from university research into the real healthcare sector.
HSE University Installs Geoscan Station at IIT Bombay
A Russian ground station for receiving SONIKS satellite data has been installed on the campus of the Indian Institute of Technology Bombay (IIT Bombay). Developed by Geoscan, the system will become part of a mirror laboratory project run jointly by HSE University and one of India’s leading universities.
HSE MIEM and MTS Launch Workshop on Innovative Solutions in Communication Networks
The HSE Tikhonov Moscow Institute of Electronics and Mathematics (MIEM) and MTS are launching a joint workshop in which students will work at the intersection of communications network engineering, data analysis, and digital technologies. The project is designed as a practice-oriented learning format, enabling students to tackle real industry challenges alongside company engineers and MIEM specialists. Registration to participate in the workshop is open until April 15, 2026.
HSE Unveils Anthropomorphic Courier Robot
From April 1 to 3, 2026, the Fourth Robotics Festival took place, with the HSE Faculty of Computer Science acting as the main organiser. The event featured the presentation of the anthropomorphic courier robot Arkus. The humanoid was introduced by the Institute for Robotic Systems, established jointly by HSE University and the EFKO Group of Companies.
‘It Is a Great Honour for Us to Be Partners’
In late March 2026, an official meeting took place between a delegation from HSE University and delegations from Vietnam National University, Hanoi (VNU); the Government of the Socialist Republic of Vietnam; and the Embassy of Vietnam in the Russian Federation. The participants discussed key areas of cooperation that will help strengthen ties not only between the universities, but also between the two countries.
How the Brain Processes a Word: HSE Researchers Compare Reading Routes in Adults and Children
Researchers from the HSE Center for Language and Brain used magnetoencephalography to study how the brains of adults and children respond to words during reading. They showed that in children the brain takes longer to process words that are frequently used in everyday speech, while rare words and pseudowords are processed in the same way—slowly and in parts. With age, the system is reorganised: high-frequency words shift to a fast route, whereas new letter combinations are still analysed slowly. The study was published in the journal Psychophysiology.
How Neural Networks Detect and Interpret Wordplay: New Insights from HSE Researchers
An international team including researchers from the HSE Faculty of Computer Science has presented KoWit-24, an annotated dataset of 2,700 Russian-language Kommersant news headlines containing wordplay. The dataset enables an assessment of how artificial intelligence detects and interprets wordplay. Experiments with five large language models show that even advanced systems still make mistakes, and that interpreting wordplay is more challenging for them than detecting it. The results were presented at the RANLP conference; the paper is available on Arxiv.org, and the dataset and the code for reproducing the experiments are available on GitHub.
HSE Holds Exams, Quizzes, and Selection Rounds for School Students in Tashkent and Bishkek
More than 3,000 international school students took part in the INTO HSE International Olympiad, whose award ceremonies were held in Tashkent and Bishkek in March 2026. The university’s outreach events also included final examinations, presentations of academic programmes, and on-site selection tests for prospective applicants. In Uzbekistan and Kyrgyzstan, nearly 200 participants received diplomas as winners and prize-winners. The best of them will be eligible to apply for state-funded places at HSE.
BRICS International School Held in Delhi
The results of the BRICS International School: New Generation, which was held in Delhi, proved that young people have become key participants in the global dialogue. The event brought together 200 young leaders from leading universities and expert centres in India. The programme was organised by the BRICS Expert Council–Russia, based at HSE University, together with the Russian House in New Delhi with the support of the Ministry of Foreign Affairs of the Russian Federation.