Doctoral School of Electrical Engineering 

BME-VIK, Department of Control Engineering and Information Technology

Supervisor: Gincsainé Dr. Szádeczky-Kardoss Emese

Motion planning for autonomous robots and vehicles in dynamic environments

Introducing the research area

Robotics is one of the flagship technologies of our time. Automation has led to thousands of factories and hospitals using mobile robots and robotic arms to reduce the burden on human labour. With the rise of artificial intelligence, we can now entrust robots with tasks we would never have dreamed of before. Mobile robots must be designed with different aspects in mind (e.g., speed, safety). Naturally, not all criteria can be met simultaneously, and a compromise solution is needed to ensure that the robot can move without collision between obstacles in its environment. The aim of this research is to develop novel motion planning methods that allow considering different aspects together.

Brief introduction of the research place

My research is conducted in the Control and Robotics group of the Department of Control Engineering and Information Technology at BME-VIK. Robotics plays a major role in the research group, in particular in the determination of robot trajectory and velocity profiles using motion planning algorithms. The professional knowledge and tools available in the research group contribute greatly to the success of the research.

History and context of the research

Motion planning for mobile robots in dynamic environments is a complex task, as there are moving obstacles in the robot's workspace in addition to static obstacles. If a map of the robotic environment is available, global motion planning algorithms [1], [2] can be applied. Otherwise, the robot can only access information through its sensors, in which case reactive motion planning algorithms can be applied [3], [4], [5]. The main goal of a given motion planning algorithm should be to achieve collision-free motion between a given initial position and a given target position.

For the best-known reactive motion planning algorithms (Dynamic window (DW) method [6], Artificial Potential Field (APF) method [7], Velocity Obstacle (VO) method [3], Inevitable Collision State method [8]), the fastest target arrival is the main priority besides the realization of collision-free motion planning. Other aspects or criteria for motion planning (e.g., lane keeping, compliance with traffic rules) are implemented at a different control level (if they play a role in the motion planning) for these motion planning algorithms. Furthermore, in the case of the fastest targeting method, there is the possibility of a collision between the robot and its environment in the case of uncertain sensor information.

The research goals, open questions

The main goal of my research is to develop a novel motion planning method for dynamic environments, based on the fundamental properties of the VO method, which can simultaneously consider different motion planning aspects at the reactive planning level. My first goal is to ensure that the motion planning algorithm can implement safety and fast targeting properties according to a given (task-dependent) preference. Then, the goal is to extend the motion planning algorithm to the extent that the lane-keeping algorithm can be implemented at the motion planning level. The consideration of the basic traffic rules and traffic regulations is another criterion for motion planning, the realization of which is the goal of my work.

Next, the aim is to implement a motion planning algorithm that can consider the reliability of the adaptively varying information (e.g., position, velocity) received from the obstacles, and then select the velocity vector for the robot in each sampling time unit. As an extension of the algorithm, it is assumed that the uncertainty of the sensor information varies adaptively as a function of the distance of the obstacle from the robot.

Furthermore, the objectives include the introduction of a novel Particle-filter based state estimation method, which can be used to estimate the state vector of obstacles in the robotic workspace using the LiDAR sensor measurement data.

Methods

In my research, I used the basic properties of the Velocity Obstacles (VO) method. Both the obstacles and the robot are represented by disk-shaped objects. Initially, we reduce the robot's radius to zero by increasing the radii of the obstacles with the robot's radius. Using this method, the set of velocities (VO set) can be determined for the agent at each sampling time instant from which, given a velocity vector, a collision between the robot and the obstacle would occur at a given future time instant. Subtracting the set of collision-inducing velocities from the set of Reachable Velocities (RV) gives the set of Reachable Avoidance Velocities (RAV). Using different strategies, by selecting a velocity from this RAV space, the robot can achieve collision-free motion between the agent and its workspace.

Figure 1: Representation of the collision-inducing velocity space regions in the robotic workspace

 

The estimation of obstacle states (position and velocity vectors) can be completed by improving the so-called Particle filter algorithm. In a review of previous literature, the Particle filter was used to determine the robot's own state using measurement data from sensors installed on the robot. The particle filter uses weighted particle set to determine the estimated state. A particle represents the possible state (position, velocity) of an obstacle, and its associated weight determines the probability that the obstacle has the properties of that particle. The steps of the algorithm include updating the weights, estimating the state, resampling, and updating the state of the particles.

The measurement accuracy of the sensor installed on the robot greatly affects the accuracy of the measurements and thus that of the overall state estimation method. The state estimation method used a LiDAR (Light Detection and Ranging) sensor, which performs the distance measurement task based on the basic properties of optical reflection.

Results

Cost function-based motion planning

I have introduced a novel method, whereby both speed and safety can be considered simultaneously in motion planning. I named this method Safety Velocity Obstacles Method (SVO) [I.], [II.], [III.]

I have introduced a novel method that allows the agent to consider the basic traffic rules in the course of its movement; and this algorithm was named Traffic Regulation Velocity Obstacle (TRVO) [IV], [V]. I extended the right-hand rule-based motion planning to left-hand traffic [IX].

 

Figure 2: The robot in blue in the CoppeliaSim (VREP) simulation environment is planning its motion by overtaking the obstacle in front of it from the left side, following the traffic rules, to reach the target position

 

In my work, I have developed a motion planning algorithm that is capable of achieving collision-free target reaching for the robot in straight lanes [VI] and for general shape curved lanes given by second-degree Bézier curves [VII], taking into account the lane-keeping algorithm.

 

In summary, I have developed a novel reactive motion planning algorithm using the fundamentals of the VO method, which can consider different criteria in parallel at the reactive motion planning level by applying a cost function-based minimization to perform collision-free motion planning between the agent and its environment.

Uncertainty-based reactive motion planning

Motion planning frequently obtains inaccurate information about obstacles in the robot's workspace, which makes it difficult for the agent to successfully perform collision-free motion.

I extended the previously introduced motion planning algorithm to consider different uncertainty factors for different obstacles [VIII], [IX]. Based on this, the motion planning is executed further away from the obstacle with higher uncertainty, while for obstacles with low uncertainty, motion planning is allowed to consider maneuvers close to the obstacle. Subsequently, I also developed an algorithm for adaptively varying uncertainty [X.].

 

Figure 3: the video illustrating the robot's targeting when the two (blue and purple) obstacles have different uncertainty parameters (α). The moving robots with different colors illustrate the result of collision-free motion planning for different cases. The β velocity parameter also varies for different cases.

 

I have introduced a novel particle-filter based state estimation method, which can estimate the position of obstacles in the robot's workspace [XI] using the measurement by the LiDAR sensor installed on the agent, and by extending the method, the velocity vector [XII].

 

Figure 4: LiDAR sensor measurement for one obstacle. The figure on the left shows the LiDAR sensor measurement result, estimated obstacle distance (z_distance), and angle (z_angle). The right figure shows the LiDAR sensor installed on the mobile robot we built.

Expected impact and further research

The results so far have been published in several national and international conference papers, and two English-language journal articles described the various motion planning algorithms introduced. We intend to publish further results in national and international journal articles. The impact of the research results will be enhanced by the upcoming DAAD fellowship, which will provide the opportunity to collaborate with a German research group.

In the future, our motion planning algorithm could be used for collision-free motion planning of small mobile robots performing transport tasks in factories and hospitals. By extending the motion planning algorithm to car-like mobile robots, the method could also be used for safe, collision-free motion planning of self-driving cars. This promises many opportunities for the use and improvement of this motion planning algorithm in the future.
 

Publications, references, links

List of corresponding own publications.

 

[I.] Emese, Gincsainé Szádeczky-Kardoss; Zoltán, Gyenes: Velocity obstacles for car-like mobile robots: Determination of colliding velocity and curvature pairs; ADVANCES IN SCIENCE TECHNOLOGY AND ENGINEERING SYSTEMS JOURNAL 3: 1 pp. 225–233., 9 p. (2018)

[II.] Zoltán, Gyenes; Emese, Gincsainé Szádeczky-Kardoss Emese: Motion planning for mobile robots using the Safety Velocity Obstacles method, In: Drótos, Dániel; Vásárhelyi, József; Czap, László; Ivo, Petráš (eds.) Proceedings of the 19th International Carpathian Control Conference (ICCC 2018), Szilvásvárad, Hungary, IEEE, (2018) pp. 389–394., 6 p.

[III.] Zoltán, Gyenes; Emese, Gincsainé Szádeczky-Kardoss: Mobilis robotok mozgástervezése az SVO és APF módszerekkel, In: Bihari, Erika; Molnár, Dániel; Szikszai-Németh, Ketrin (eds.) Tavaszi Szél – Spring Wind 2019: III. Kötet, Budapest, Hungary: Doktoranduszok Országos Szövetsége, (2020) pp. 42–55., 14 p.

[IV.] Zoltán, Gyenes; Emese, Gincsainé Szádeczky-Kardoss, Motion planning for mobile robots using Traffic Regulation, In: Kiss, Bálint; Szirmay-Kalos, László Proceedings of the (eds.) Workshop on the Advances of Information Technology, Budapest, Hungary (2019) pp. 92–97., 6 p.

[V.] Zoltán, Gyenes; Emese, Gincsainé Szádeczky-Kardoss: Traffic Regulation Velocity Obstacles method, In: Nawrocka, A.; Kot, A. (eds.) 20th International Carpathian Control Conference, ICCC 2019, Wieliczka, Poland, IEEE, (2019) Paper: 8766055, 6 p.

[VI.] Zoltán, Gyenes; Emese, Gincsainé Szádeczky-Kardoss: A novel concept of lane-keeping algorithms for mobile robots, In: Szakál, Anikó (eds.) IEEE 17th International Symposium on Intelligent Systems and Informatics Proceedings, Sisy 2019, Subotica, Serbia: IEEE Hungary Section, (2019) pp. 47–52., 6 p.

[VII.] Zoltán, Gyenes; Emese, Gincsainé Szádeczky-Kardoss: Novel Motion Planning Method for Mobile Robots Using Velocity Obstacle, ACTA POLYTECHNICA HUNGARICA 17: 9 pp. 221–240., 20 p. (2020)

[VIII.] Zoltán, Gyenes; Emese, Gincsainé Szádeczky-Kardoss: Velocity selection for mobile robots using different strategies and probability, In: Kiss, Bálint; Szirmay-Kalos, László (eds.) Proceedings of the Workshop on the Advances of Information Technology 2020, Budapest, Hungary: BME VIK Irányítástechnika és Informatika Tanszék, (2020) pp. 142–147., 6 p.

[IX.] Zoltán, Gyenes; Emese, Gincsainé Szádeczky-Kardoss: Rule-based velocity selection for mobile robots under uncertainties, In: IEEE, Publisher (eds.) IEEE 24th International Conference on Intelligent Engineering Systems Proceedings (INES 2020), Reykjavik, Iceland, IEEE, (2020) pp. 127–132., 6 p.

[X.] Zoltán, Gyenes; Emese, Gincsainé Szádeczky-Kardoss: Motion planning for mobile robots using uncertain estimations about the environment, In: Kiss, B; Harmati, I; Taqvi, Z (eds.) 2020 23rd International Symposium on Measurement and Control in Robotics (ISMCR): Budapest, Hungary, IEEE (2020) pp. 1–6., 6 p.

[XI.] Zoltán, Gyenes; Emese, Gincsainé Szádeczky-Kardoss: Particle filter-based obstacle’s position estimation using Lidar measurement data, In: Kiss, Bálint; Szirmay-Kalos, László (eds.) Proceedings of the Workshop on the Advances of Information Technology (WAIT) 2021, Budapest, Hungary : BME Irányítástechnika és Informatika Tanszék (2021) pp. 101–108. , 8 p.

[XII.] Zoltán, Gyenes; Emese, Gincsainé Szádeczky-Kardoss: Particle filter-based perception method for obstacles in dynamic environment of a mobile robot, In: IEEE, Publisher (eds.) IEEE 25th International Conference on Methods and Models in Automation and Robotics Proceedings (MMAR2021), Międzyzdroje, Poland, IEEE, (2020), 6 p. (accepted)

 

List of references.

 

[1]   S. M. LaValle. Planning Algorithms. Cambridge University Press, 2006.

[2]   Chand, Praneel and Carnegie, Dale A. A two-tiered global path planning strategy for limited memory mobile robots. Robotics and Autonomous Systems, vol. 60, no.2, pp. 309–321, 2012

[3]   Paolo Fiorini and Zvi Shiller: Motion Planning in Dynamic Environments using Velocity Obstacles, The International Journal of Robotics Research July 1998 vol. 17 no. 7 760–772.

[4]   Kovács, Bence and Szayer, Géza and Tajti, Ferenc and Burdelis, Mauricio and Korondi, Péter. A novel potential field method for path planning of mobile robots by adapting animal motion attributes. Robotics and Autonomous Systems, 82: 24–34, 2016.4.

[5]   Michael Hoy, Alexey S. Matveev and Andrey V. Savkin: Algorithms for collision-free navigation of mobile robots in complex cluttered environments: a survey, Robotica (2015) volume 33, pp. 463–497. © Cambridge University Press 2014

[6]   D. Fox, W. Burgard, and S. Thrun, “The dynamic window approach to collision avoidance,” IEEE Robot. Autom. Mag., vol. 4, no. 1, pp. 23–33, Mar. 1997.

[7]   Malone N, Chiang HT, Lesser K, et al. Hybrid Dynamic Moving Obstacle Avoidance Using a Stochastic Reachable Set-Based Potential Field. IEEE Transactions on Robotics. 2017;33(5):1124–1138.

[8]        Fraichard T, Asama H. Inevitable collision states – A step towards safer robots. Advanced Robotics. 2004;18(10):1001–1024.