The development of Intelligent robot technology -- Motion intelligence

Sports intelligence

A renowned robot scientist at MIT believes that autonomous robot navigation should answer three questions, "Where am I?" ", "Where I am going? ", "How should I go there? In this paper, three problems of robot localization, planning and control are described respectively. Robot motion planning is one of the three core problems to solve robot navigation.

As one of the core problems in robotics, motion planning is the fundamental technology to solve the coexistence of robots and human beings. Motion planning mainly addresses the problem of how a robot can perform a specified action without accidentally colliding with the physical world.

Research on robot motion planning emerged in the 1960s. In 1978, Lozano-Perez and Wesley first introduced the concept of pose space (C-space) to construct the planner, which was an epoch-making revolution for the modern motion planning problem. In C - space, every posture only represent the position and posture of robot in physical space, the robot in the pose is abstracted as a point in space, so that the motion planning problem into a posture in the space of the reign of find a from the starting position to target position of continuous path, greatly simplifies the programming calculation. In 1987, J. P. Laumond introduced incompleteness in mechanical systems into robot motion planning to solve the problem of self-parking. Since then, nonholonomic motion planning has become a new research hotspot until today.

Path planning of mobile robots can be regarded as a simple special case of motion planning. The so-called "path" refers to a specific sequence of robot poses in pose space, regardless of the time factor of robot poses. The "trajectory" is related to when each part of the path is reached, emphasizing temporality. Robot motion planning is planning for "track", according to the similarities and differences of search strategy and environment modeling, the planning method in general can be divided into: planning based on free space geometry structure, forward search algorithm, the rise in recent years to solve high-dimensional space attitude and motion planning in complex environment, for the purpose of motion planning based on random sampling and other intelligent planning method.

Planning methods based on geometric construction include viewable, tangent diagram, Voronoi diagram and exact (approximate) raster decomposition methods. Path planning is the process of searching. No matter what kind of planning algorithm, it will ultimately come down to the problem of searching a continuous path in a certain space that satisfies a certain criterion. To describe the free space of the environment by means of geometric construction, graphs are generally formed (raster is regarded as a special kind of graph), and graph search is a very important step to complete the trajectory planning. Forward graph search algorithm is A search algorithm from the starting point to the target point, commonly used including greedy algorithm, Dijkst RA algorithm, A * algorithm, D * algorithm (Dijkst RA algorithm variant) and artificial potential field method, etc.

The computational complexity of the above algorithms is exponentially related to the degree of freedom of the robot, so they are not suitable for solving the planning of high degree of freedom robots in complex environments, and they are not suitable for solving the planning with differential constraints. In 1990, Barraquand and Latombe proposed the RPP(Randomized PotentialPlanner) planning algorithm, which was used to overcome the local minima of artificial potential field method and the efficiency problem of planning in high-dimensional attitude space. The emergence of PRM(probabilistic roadmap) in 1994 and bold-exploring Random Tree (RRT) in 1998, two motion planning methods based on random sampling, has set off a new upsurge of robot motion planning research. These algorithms are suitable for solving the motion planning problem of high degree of freedom robot in complex environment.

Path planning is a combination of environment model and search algorithm. The planning process is not only a search process, but also a reasoning process. Many optimization and reasoning techniques in artificial intelligence have also been applied to mobile robot motion planning, such as genetic algorithm, fuzzy reasoning and neural network, which play a great role in mobile robot motion planning. The genetic algorithm solves the path planning problem by expressing the individual path as a series of halfway points in the path and converting them into binary strings. First, the path population is initialized, and then genetic operations such as selection, crossover, replication, mutation are performed. After several generations of evolution, it stops evolving and outputs the current optimal individual as the next node in the path. The fuzzy planner takes the current environment obstacle information as the input of the fuzzy inference engine, and the inference engine outputs the desired steering Angle and speed of the robot. The basic principle of neural network planner is to take the environmental obstacles as the input information of neural network, which is processed in parallel by neural network, and the output layer of neural network outputs the desired steering Angle and speed, etc., to guide the robot to avoid obstacles and drive until it reaches the destination. These intelligent reasoning methods are similar to the methods based on geometric construction. With the increase of robot degrees of freedom and the increase of environment complexity, there are efficiency problems.

Generally, a good planning algorithm usually has the following characteristics: rationality, completeness, optimality, real-time, adaptability to environmental changes, satisfying constraints, etc. However, no matter what kind of robot path planning belongs to and what kind of planning algorithm is used, the following steps should be basically followed: 1) Build an environment model, that is, build a relevant model after abstracting the real world in which the robot is located; 2) Search collision-free path, that is, search algorithm to find qualified path in the space of a certain model. At present, the difficulties of motion planning mainly include difficult area problem, dynamic environment problem, real-time planning problem, ANYTIME planning problem, optimal planning problem, and special coverage path planning problem.

The motion planning algorithm of mobile robot is accompanied by the development of mobile robot to meet the needs of the robot and develop. Today, unmanned ground, underwater, aerial robots develop rapidly, soccer robot competition is in full force, and the robot is moving toward miniaturization and multi-robot cooperation direction. With the need of planetary exploration and unmanned warfare, the research of robots is increasingly focused on autonomous navigation in the complex environment with rugged terrain and movement obstacles. In order to meet the needs of the development of mobile robots, motion planning is and will be developed to high-dimensional DOF robots, multi-robot coordination, and dynamic unknown environment planning. The intelligent planning method based on random sampling combined with other motion planning methods will be the focus and hotspot of research.

The comparison of general programming algorithms shows that the following aspects should be paid attention to in the research and application of mobile robot motion planning:

1) less degrees of freedom robot in simple environment, such as indoor, outdoor, flat, straight roads, etc., when low speed navigation or long-range ups and downs of cross-country environment, can need not consider dynamics characteristics of the robot, based on free space geometry structure and graph search matching algorithm is more efficient, practical, the algorithm in the aspect of rationality of defects by the control strategy.

2) In complex environments, such as rugged cross-country terrain and complex underwater environment, high-speed navigation, such as military applications and field rescue, requires high real-time navigation requirements for robots with less freedom, and the dynamic characteristics of the robot must be considered.

3) Robots with high degrees of freedom, such as rovers and space shuttles, have relatively low requirements on the completeness of algorithms when navigating autonomously in complex environments, and can allow replanning when planning fails. In order to ensure the efficiency of the algorithm, the deterministic algorithm is not applicable, and the planning algorithm based on random sampling has a stronger ability to solve such problems. However, under the premise of ensuring the efficiency of the algorithm, the completeness of the algorithm is improved as far as possible to achieve more reliable planning.

4) A strategy combining intelligent planner with geometric construction and random sampling algorithm should be sought to reduce the parameter selection of the planning algorithm and manual intervention in the planning process, and the algorithm should be optimized to reach or approach the optimum of a certain index (such as time, distance, energy consumption, etc.).