Projects:2018s1-170 Intelligent Parking Control for Autonomous Ground Vehicles

I. Introduction

I.I. Background

In recent years, with the rapid increasing in the number of private cars, parking problems in large and medium-sized cities have become more and more serious. People in daily life have been accustomed to handing over problems to artificial intelligence. Therefore, there is an urgent need to design an intelligent parking system. The intelligent parking system integrates computer networks, video surveillance, image recognition and processing, and automatic control technologies to manage the vehicles automatically in the parking lot. Compared to the traditional parking lot, the intelligent parking system can accurately distinguish in-system vehicles and exotic vehicles. It can also save management personnel expenses, improve work efficiency and economic efficiency. Moreover, the smart parking system has good scalability and it can be applied to various unmanned scenarios.

I.II. Objective

Intelligent Parking Control for Autonomous Ground Vehicles project involves in designing a multi-vehicle system which includes 4 robots for autonomous location, guidance, and parking in a congestion parking area. Each robot represents an individual ground vehicle which can independently select best visual parking lot while avoiding visible obstacles. Obstacles avoidance not only including visual still obstructions, but also including moving visual obstacles. Camera installed to track the velocity of moving obstacles, and algorithm would be used for vehicles to avoid those obstacles.

I.III. Motivation

This project is motivated by simplifying the difficult and complicated parking process when driving a vehicle and improving the efficiency in group parking control. This system is aimed for multi-platform, future work may extend it to UAVs, UUVs and some other kind of unmanned applications.

II. Literature review

II.I. Environmental data detection

Environmental data detection is the use of computer algorithms to perform image processing on digital images and analyze the resulting environmental data. Since the image is defined in two dimensions (possibly more), environmental data detection may be modeled in a multidimensional system (Ramya R, Anand Kumar S, Krinish N K, Suraj V, 2015). The goal of environmental data detection is to improve the visualization of locations of targets by optimizing these physical parameters. The processing parameters need to be chosen correctly to overcome the opposite relationship between contrast and latitude, while at the same time getting the exact position of the desired target.

II.II. Path planning

For the path planning of a single robot, we only need to consider the shortest distance from the starting point to the destination. According to Dijkstra's algorithm, we can divide the map captured by the camera into several squares. By calculating the heuristic equation of F = G + H for each square, the path with the shortest distance could be determined. It means the smaller value of F, the shorter distance the robot will travel. When considering multiple robots, we first need to find the shortest distance from each robot to different parking spaces according to Dijkstra's algorithm and then find the optimal solution for multiple robots' selection of parking spaces in terms of Hungarian algorithm. In addition, since the Hungarian algorithm is a method that can avoid the conflict between robots, we do not need to consider the case that multiple robots select the same parking space at the same time.

II.III. Virtual field force

Ali Marzoughi (2017) assumed a methodology for robots to avoid obstacles. Regarding each visual obstacle is doing a repulsive force to a pointwise vehicle. At the meantime, the destination is doing an attractive force to the vehicle. Velocity of the moving vehicle could be influenced by these two kinds of force. Magnitude of each force is changed in real time regarding the velocity and distance of the obstacles and the destination.

II.IV. Motion support

In the execution part, QBot2 can integrate with MATLAB/Simulink software to provide real-time communication and interfacing to the components of the QBot 2. According to a typical kinematics model that computes the robot chassis speed Vc, turning rate ω, the wheel speed Vr and Vr, the wheel separation distance d to calculate the x and y-axis coordinates, and to control and move the QBot 2 in the scheduled path. For execution, the first thing needs to do is to find path and location based on image features and obstacle avoidance algorithm. This information, along with the location and orientation of the robot chassis, can be used for autonomous map building. Next, we should sign motion planning involves the creation of motion commands for the QBot 2 based on a series of goal positions or way-points.

III. Abstract

Intelligent Parking Control for Autonomous Ground Vehicles project involves in designing a multi-vehicle system which includes 4 robots. Robots in this system are QBOT2 and are integrated with camera to detect environmental information. Each robot in the system is individual and able to independently choose its parking space and avoid collision with obstacles and other vehicles. The motivation of this project is to provide a simplified, efficient parking environment. In addition, future work may extend it to UAVs, UUVs and some other kind of unmanned applications.

IV. Implementation

IV.II Decision Making

This part focuses on decision-making. The major function is making the parking choices and requires data to indicate the availabilities of the parking space and real-time updates on the obstacles in the experimental environment, and this is depending on the inputs from the image processing module. By analysing the inputting data, the vehicle could schematize an optimised routine to find an optimal parking spot.

In this project, the choice of the optimal parking space will be judged according to the shortest distance that each agent needs to move.

For this project, a total of three algorithms were tested to find the optimal parking space which are Dijkstra algorithm, Ant Colony algorithm, and Hungarian algorithm. They will be analysed and compared in detail. The Hungarian algorithm is chosen to find the optimal parking space as the best algorithm at the end.

The Hungarian algorithm is an algorithm applied to the distribution problem. The core idea of the Hungarian algorithm is to complete the assignment by maximizing or optimally matching the bipartite graph. For example, if a worker needs to work in n locations, then the Hungarian algorithm can optimally allocate according to the characteristics of each worker or the shortest distance from each worker to the workplace.

Hungarian algorithm is one of the best algorithms to solve the allocation problem, because there will be no duplicate allocation [16]. In this project, the choice of the optimal parking space can also be regarded as an allocation problem. Therefore, Hungarian algorithm can be used to solve the problem of choosing the optimal parking space without choice conflict. The specific implementation can be divided into four parts:

According to the result of the image processing, the coordinates of each parking space and vehicle can be obtained. Based on the distance function of |P_1 P_2 |=√(〖(x_1-x_2)〗^2+〖(y_1-y_2)〗^2 )，The distance matrix of each vehicle to each parking space can be listed.

Therefore, each row of this matrix represents the distance of one vehicle to eight parking spaces. For example, the first row represents the distance of vehicle A to eight parking spaces respectively, and the second row represents the distance of vehicle B to eight parking spaces respectively.

All the values in each row of the matrix minus the minimum value of the row will get a completely new matrix. Then all the values of each column of the new matrix minus the minimum value of the column. There will be a matrix with multiple zeros being obtained and crossing all the zeros with horizontal and vertical lines.

If the total number of lines that passed zero is equal to the number of rows or columns of the original matrix, the best match can be found. Otherwise, the minimum value of the area that is not covered by the line passing through zero needs to be found, then using the minimum value repeat the second step until the total number of lines is equal to the number of rows or columns of the original matrix.

A new matrix containing only 1 and 0 will be obtained. By comparing the newly obtained matrix with the original matrix, the global optimal solution can be determined. It means that the position corresponding to 1 in the new matrix is the optimal parking space.

IV.III Collision-free Path Planning

IV.III.I Algorithm decision

As it mentioned above, PSO, Grid and VFF are all considered to achieve real-time obstacle avoidance. In order to achieve a good consequence in this project, all three algorithms are compared.

The advantage of PSO algorithm is that it is simple in calculation. For each agent, it only needs to know its personal coordinate and condition and will achieve better path plans as the increase of experimenting time. However, PSO mainly aims to solve the collision problem within a group of agents, which means the agents in the group have similar start point and destination. In this project, the coordinate of destination could be similar but the start point of each vehicle is random. Moreover, PSO algorithm uses global coordinate system, which is difficult to achieve without satellite cameras. Therefore, PSO is not feasible in this project.

Grid methodology is a classic and effective way to achieve obstacle avoidance. However, as mentioned above, Grid methodology does not perform well in doing dynamic obstacle avoidance. As the combination of Grid and Artificial Potential Field, VFF uses the location of obstacles which detected in Grid and adding artificial force to show the velocity changes and avoid the obstacles, which is effective and reliable. Therefore, VFF is chosen as the basic thesis of collision-free path planning in this project.

IV.III.II Simplified VFF

The classic VFF uses pointwise methodology to compute the virtual field force. Each visible point on obstacles does a virtual filed force on the agent which is regarded as a particle. At the mean-time, each point in the ‘safe zone’ does an attractive virtual field force. However, in real-world scenario, comparing to the experimenting parking space, the agents are not small enough to be regarded as particles. Collision could happen if using VFF algorithm without consider the initial radium of the agents. On the other hand, if the virtual force is calculated as pointwise, it is a huge amount of computing especially for multiple vehicles, which will increase the reaction time. To make final product qualified, it is necessary to simplify the classic VFF algorithm. Considering the rover used in this project is QBot2, which is with circle shape, the model of the agent could be settled as a circle with a radium r_a. In this project, the exclusive destination for the agent is chosen parking spot. Therefore the ‘safe zone’ could be simplified as a single particle d. Main obstacles may exist in the system are walls and other obstacles. Since walls could be regarded as the boundary of the experimenting environment, other obstacles could be simply assumed as cylinders or approximate cylinders. Each virtual filed force f_j could be worked on the agent along the obstacle centre pointing the agent centre direction.

VI. Members

VI.I Group member

Chenyuan Wang;

Chengcheng Mao;

Dahai Hu;

Junxi Liu;

VI.II Supervisors

Prof. Peng Shi;

Prof. Cheng-Chew Lim;

VI.III Advisors

Yutong Liu;

Bing Yan;

Xin Yuan

VII. References

Quanser Inc., QBOT 2 Workbook – Student, 2015

Quanser Inc.,QBOT 2 - User Manual, 2015

Ercan Taskiran , Yilmaz Durna and Hasan Kocer, “Wi-Fi Control of Mobile Robot Motion Types Based on Differential Drive Kinematics Modelling Approach” in Advanced Technology & Science, April 2016, pp 170-173

Yu, H Y 2010, ‘Multi-model distribution problem based on Hungarian algorithm’, Delivery Technology, vol. 29, no. 11, pp. 74-75.

The Qbot-2-Quarc 2018, digital photograph, Quanser, viewed 1 March 2018,<https://www.quanser.com/products/qbot-2-quarc>.

The algorithm of Path Planning 2017, CSDN, Technology Blog, viewed 13 March 2018,<https://blog.csdn.net/u012907049/article/details/78037686>.

Path Planning of Robots 2017, CSDN, Technology Blog, viewed 14 March 2018,<https://blog.csdn.net/darren2015zdc/article/details/73495441>.

Y. Jo, J. Jang and J. Paik, "Camera orientation estimation using motion based vanishing point detection for automatic driving assistance system", 2018 IEEE International Conference on Consumer Electronics (ICCE), 2018.

G. Zheng, Z. Liang and J. Li, "Optimization of an Intelligent Controller for Parallel Autonomous Parking", TELKOMNIKA Indonesian Journal of Electrical Engineering, vol. 11, no. 2, 2012.

T. Tao, "Fuzzy automatic driving system for a robot car", 2014 International Conference on Fuzzy Theory and Its Applications (iFUZZY2014), 2014.

J. Crowley, "Navigation for an intelligent mobile robot", IEEE Journal on Robotics and Automation, vol. 1, no. 1, pp. 31-41, 1985.

H. H. Meng, “The development and trend of automatic driving,” East China Science Technology, vol. 9, pp. 68-70, Aus. 2014.

M. Wu, B. Wu and H. Song, "Application of Java — Based optimization Dijkstra algorithm in parking lot berth guidance", 2017 8th IEEE International Conference on Software Engineering and Service Science (ICSESS), 2017.

F. Cuesta, A. Ollero, “Intelligent Mobile Robot Navigation”, Springer Tracts in Advanced Robotics, vol. 16, pp. 7-49, 2005

Risald, A. Mirino and Suyoto, "Best routes selection using Dijkstra and Floyd-Warshall algorithm", 2017 11th International Conference on Information & Communication Technology and System (ICTS), 2017.

H. Wang, F. Zhang and P. Cui, "A parking lot induction method based on Dijkstra algorithm", 2017 Chinese Automation Congress (CAC), 2017.

Yujin and G. Xiaoxue, "Optimal Route Planning of Parking Lot Based on Dijkstra Algorithm", 2017 International Conference on Robots & Intelligent System (ICRIS), 2017.

N. Navimipour and B. Milani, "Replica selection in the cloud environments using an ant colony algorithm", 2016 Third International Conference on Digital Information Processing, Data Mining, and Wireless Communications (DIPDMWC), 2016.

L. Zhang, K. Rao and R. Wang, "T-QoS-aware based parallel ant colony algorithm for services composition", Journal of Systems Engineering and Electronics, vol. 26, no. 5, pp. 1100-1106, 2015.

K. Zhao, "Multiple-Agent Task Allocation Algorithm Utilizing Ant Colony Optimization", Journal of Networks, vol. 8, no. 11, 2013.

C. LIU, "Improved ant colony genetic optimization algorithm and its application", Journal of Computer Applications, vol. 33, no. 11, pp. 3111-3113, 2013.

R. Jonker and T. Volgenant, "Improving the Hungarian assignment algorithm", Operations Research Letters, vol. 5, no. 4, pp. 171-175, 1986.

Huang, S. and Chen, C. (2013). P.131: A Significant Multi-Touch Algorithm for the Tracking Problem Based on the Hungarian Algorithm. SID Symposium Digest of Technical Papers, 44(1), pp.1505-1508.

Ji, P., Lee, W. and Li, H. (1997). A new algorithm for the assignment problem: An alternative to the Hungarian method. Computers & Operations Research, 24(11), pp.1017-1023.

Cheng, Y., Zhang, P. and Cao, B. (2015). Weapon Target Assignment Problem Solving Based on Hungarian Algorithm. Applied Mechanics and Materials, 713-715, pp.2041-2044.