Trajectory planning
Automatic trajectory planning is one of the key functionalities of systems, the behavior of which can be called "intelligent". Such systems include not only mobile robots (robotic vacuum cleaners, multi-rotor drones, etc.), but also, for example, computer game characters, etc.
As part of this direction, you are invited to participate in the development of methods and algorithms for trajectory planning, applicable both in the tasks of navigation of unmanned aerial vehicles and for other types of tasks, for example, pedestrian and / or bicycle navigation in the city, indoor navigation, etc.
Required skills:
  • C ++ (development is carried out in the QtCreator environment)
  • Ability to use version control systems (GIT)
  • Ability to read scientific and technical literature (articles, textbooks, technical documentation, manuals) in English
  • Knowledge of PostgreSQL is a plus for individual projects in the framework of the direction (those projects that are related to the processing of real geo-data
Key words:
Automatic planning, trajectory planning, heuristic search, A *, Theta *, LIAN, JPS, RRT.
Entry points to the project:
  • George D., Hawkins J. Towards a mathematical theory of cortical micro-circuits // PLoS Comput. Biol. 2009. Vol. 5, № 10. P. e1000532.
Sample Topics:
  • Trajectory planning as a heuristic path finding problem on graphs of special structure (1, 2 course)
  • Methods and algorithms for finding a path on a graph
  • Heuristics for reducing the search space
  • Types of graph models arising in trajectory planning problems
  • Trajectory planning methods and algorithms for unmanned aerial vehicles (3-4 course)
  • RRT and PRM planning approaches
  • Taking into account the dynamics of motion of the control object (structure of the search space)
  • Taking into account geometric constraints when planning trajectories on a plane (2-4 courses)
  • Algorithms Theta *, ARC-Theta *, LIAN
  • Trajectory planning for a coalition of agents (2-4 courses)
  • Centralized and decentralized approaches to solving the problem
  • Elimination of local conflicts
  • Optimal and non-optimal algorithms
Participation in work in the direction of "Trajectory planning" will allow you to:
    • Get acquainted with the fundamental heuristic search algorithms (such as, for example, A *), which are in demand not only in trajectory planning, but also in many other areas of computer science;
    • Implement (with your own hands, from scratch) one of the many trajectory planning algorithms (A *, Theta *, JPS, LIAN, etc.), which significantly improves the design and programming skills (a high-quality implementation implies about 5-10 classes, and 1500 significant code lines);
    • Embed your implementation of the algorithm into the web interface of the pathplanning.ru service to be able to demonstrate your results online 24/7 (when defending term papers, graduation papers, applying for a job, etc.);
    • Offer your own (new) trajectory planning algorithm previously unknown;
    • Successfully write / defend a term paper / graduate work and get all the necessary knowledge to continue scientific work on the topic of "artificial intelligence", "intellectual planning", "trajectory planning", "heuristic search".