Heuristic Solution for Optimized Path Finding in Smart Parking System.

DOI : 10.17577/IJERTCONV6IS15122

Download Full-Text PDF Cite this Publication

Text Only Version

Heuristic Solution for Optimized Path Finding in Smart Parking System.

Heuristic Solution for Optimized Path Finding in Smart Parking System.

Vibha S

4 sem, M.Tech SCEM, Mangaluru

Mr. Sudheer Shetty Associate Professor SCEM, Mangaluru,

Shwetha R J 4

sem, M.Tech

SCEM, Mangaluru

Abstract:- Due to increase in the number of vehicles on road, there is an arising issue for parking as well. Most of the time, there is a scarcity for available empty spaces to park the vehicles .Even if its available there is always a problem to find a traffic-free path to reach it. This situation can lead to congestion, confusion, waste of energy, vehicle blockage etc. A solution proposed to tackle the concerned issue is to have a grid based- smart parking system which gives required information about the parking occupancy status, location and path to be traversed within the parking arena. This can be achieved using an environment which supports smart camera (embedded with intelligence) and a control system for processing over the server through an end user mobile application. RFID readers are placed at the entrance and exit of parking arena for opening and closing of the gates as a part of authentication. Main working of the system is the computation process which allocates a parking slot number and its location. The route from entry point to the allocated slot is suggested by the best path search algorithm which finds an optimized path considering the obstacles in real time. This work reduces the consumption of time and money compared to existing one in real-time.

General Terms:- Path optimisation, best search algorithm

Keywords:- IoT, RFID, Smart camera, Deep learning, Grid parking


    In the current scenario, every vehicle is stopped at the entrance of parking ,security workmen manually checks for free parking slots and the vehicle is directed to park in a path as instructed or the driver goes in search of one . This scenario leads to traffic congestion and chaos while parking. To overcome this problem, real-time system can be introduced which takes care of all the related sensitive issues. It involves integrating of hardware and software in embedded systems. Considering the fact that all the vehicles on road are registered under legal norms, it is allowed to utilize this system. System is designed as follows, every entrance and exit of grid based parking space (indoor and outdoor) should have RFID readers set up and the server is fed with all the registered RFID tags of smart cars for authentication. RFID tag of every smart car entering the parking area is noted automatically and is updated to server using Raspberry-pi control system. Front end of the system is an Android application which is used to check the availability of parking slot for a particular interval of time, and also book the same in prior. On reaching the grid parking arena, user is given with the optimized path direction to reach the slot allotted. Once the user confirms his/her occupancy, the

    control system automatically updates necessary information of vehicle parked, emptied, status, time duration, vehicular details, extra parking time etc and produces all at the checkout .Some of the drawbacks of the existing system are:

    1. No Optimized path finding traversal method to reach allotted slot in both open and closed parking space.

    2. System uses dijkstras algorithm to find the shortest path for traversal but it wastes a lot of time while processing. Solutions to these two problems have been proposed in the system. Implementation of this project requires UHF RFID readers, rfid tags, Raspberry-pi, smart camera, cloud based server, android application, ESP8266 Wi-Fi module. Parking system is completely grid based which is nothing but reinforcing and dividing the ground space in the form of grid (equal sized rectangle) so that it is easy to identify the boundary of a slot allotted for vehicle parking in real-time. It is also convenient to show grid based parking system virtually through an android application for users to book the same. Once booked online, system generates a message comprising the allotted slot-number and its exact lat- long location (GPS). The vehicle uses the location received to reach the destination with efficient traversal. Following this best search path traversal, it helps to reduce congestion and traffic while parking and eliminates confusion. To analyze whether the allotted slot is available in real-time or not, we make use of Smart camera with raspberry-pi embedded which is trained with datasets to recognize whether a grid-slot is empty or occupied is detected using Convolution Neural Network algorithm (deep learning). It is shown in figure 1 below. It keeps updating the status of occupancy in the parking-spaces to the server through the control system. Overall, system is an integration of machine learning in embedded system.

    Fig 1: Occupancy detection using smart camera


    Since most of the issues are related to space and path optimization while parking of vehicles efficiently in real- time scenario, there is need for advanced technologies to tackle the problems. Some of the recent work done on this topic is as follows:

    Muftah Fraifer proposed a system which reduces the chaos involved in searching for an empty parking slot in real-time scenario [1]. The system consists of 3 major components namely parking server, microcontroller and CCTV node. Whenever the user wants reserve a parking space in prior, he will have to install and register to the application and book through it .Once you request for an empty spot, system generates a user-id and interacts with the server. The occupancy of the parking spot depends on the blob detection algorithm which uses the openCV library from Intel to differentiate whether a parking spot is occupied or not. The algorithm analyses a car in an arena in the form of rectangular grid. Whenever the car is parked it will compare the detected shape to the rectangular shape, if its smaller than the boundary, then it determines that the car is parked in that particular space. THANH NAM PHAM proposed a system which not only finds a successful parking space but also reduces the waiting time [2]. Highlight of this system is if there is no empty space available in the reserved space, it redirects to a nearest alternate path for successful parking. It consists of RFID readers at the entry to get the count of number of vehicles entering. Based on the LED display at the entry which has the information about free and total slots, vehicle is allowed to park, if the space is completely occupied, then it reroutes to another parking area. This is possible by implementation of wireless senor network. Every parking area is considered as a node of WSN with each of it having all the information about other nodes with the help of neighbor tables. Each node has local server which updates the cloud over wifi/3G/4G. The control unit of the whole system is arduino UNO which is connected to both RFID and cloud for timely update of information. It mainly controls the opening of the door after authenticating the rfid tag of the vehicle. The car par network not only has the data of all nodes but also about the distance between every node so that system can redirect to the next nearest parking slot. There is a mathematical model, simulation and real time data analysis defined which proves that overall average waiting time is only 15min for this system.

    Mohammed Y Aalsalem proposed a system called campus sense which monitors and manages the parking information in n arena [3]. GPS usage provides the exact location of vehicle. Additional feature of the system is the automatic vehicle number plate detector which helps to provide the complete information of the vehicle and its owner to find out evidence in case of damage to the vehicle while parking of it. Abhirup Khanna proposed a system which is based on cloud of things. Its feature is to store data on demand and be available for cloud integration whenever the processing unit is ready with a status update [4]. Computation of occupancy rate (0 or 1)

    is based on a mathematical model which is determined after processing the input, identity and computational functions. Initially, IR sensors determines whether the slot is empty or not, it then updates the control system (raspberry pi)using ESP8266 wifi chip with SOC embedded in TCP/IP protocol stack which allows microcontroller to access the network. Through a mobile application which runs both on android and IOS using apache cordova, user requests for a free slot to park the vehicle for the mentioned time duration and the application gives an option to choose a spot , now the system communicates and updates with server through MQTT protocol in JSON format. At the same time, sensors sense the data, updates and change the current status empty to reserved. The communication between mobile application and system is though the private network. Once the user reaches the parking pace, he has to confirm his occupancy within 5 minutes of his arrival else he will have to rebook the slot again. After the vehicle is parked, If the reserved space exceeds time duration its booked for, then he will have to pay the extra amount at the exit.

    Mahendra B M proposed a system which provides an automated parking reservation and booking service through a mobile application in advance using sensor enabled parking arena [5]. At first, user registers with adhaar-card number (authentication) and logs in to the e- parking mobile application. There are 3 main features namely profile, booking and checkout. User pre-books slot a particular duration, in response to this slot is locked. After driver reaches the parking spot, vehicle is authenticated by using the booking id given at the time of booking. Algorithm validates the time used for parking and charges for it has to paid using credit card at the exit. After the vehicle has left, status automatically changes to available for others.

    Giuseppe Amato has proposed a system which detects the occupancy of vehicle based on machine learning. It uses a HD camera which is trained with 2 huge training [6]. Raspberry-pi Camera classifies the space into occupied or empty using the intelligence its trained with.

    Oluwatimilehin Olumolade proposed a system which deals with Vehicle to infrastructure communication using a touch screen module installed in the vehicle and parking meter installed in every parking lot and its effective communication helps to find if a free space is available or not [7].

    Chihhsiong Shih proposed a system which includes vehicular positioning, mobile application for virtual booking, parking monitoring based on grid based parking space using magnetic and IR sensors for detection and its display is through the LED panel [8].

    Yujin, Ge Xiaoxue has made use of dijkstras algorithm for path traversal while parking towards the destination slot. It gives the shortest path from source node (entry point) to destination node (exit point) using combination of impedance function model and balance function for best navigation path of vehicles effectively [9]. The disadvantages of this algorithm used in this can be

    overcome by the proposed system mentioned below.


    3.1 System Design

    Outdoor and indoor parking arena uses raspberry pi as a processor which is embedded in smart camera.It plays a major

    Fig 2: Parking system design

    role in parking of vehicles smartly. Diagrammatic representation is shown above in figure 2. Control system in the smart camera does two exclusive functionality, they are:

    1. It identifies the occupancy of vehicles (whether the parking space is empty or not) using deep learning technique. It is nothing but a part of artificial intelligence which is used to train a machine in such a way that it behaves almost like a human and is able to analyze like how a human brain does to the atmost accuracy. Trained datasets consists of images of parking-spaces in all possible situation like empty slot, occupied slot with and without climatic conditions such as rainy, sunny, cloudy, images at different angles, rotated , un- rotated in convolution layers. The control system (Raspberry smart camera) is fed with datasets PQLot and CNNpark [6] which captures images in real-time of parking space at equal intervals of time, compares with existing trained sets and determines its status of occupancy and updates to the server regularly.

    2. It computes the best path for traversal and sends a notification message to the users phone about the lat- long location and the path to be taken while parking the vehicle starting from entry point to the exact allocated parking point using the A-star algorithm. This system can be implemented using single type of hardware (i.e well trained smart-cameras) within the existing parking spaces and there is no need of any extra infrastructure set-up like sensors or LED panels. This minimises the hardware failure and improves the efficiency of the system.


    Cloud based automatic vehicle parking system authenticates the registered vehicles using RFID technology at entry/exit of parking place. User searches for parking slots near me in the mobile application and the system suggests the nearest parking area with empty slots available with its location and its voice direction. Once the user has confirmed the slot and time duration required for parking, it is reserved for that particular user and payment is done either online while booking or can

    be done at the exit. The status of reserved slot (once booked) becomes unavailable for the rest of the users. The status of occupancy and calculation of optimized path is done by raspberry smart camera. Reservation and booking of parking slots happens in FIFO method. Here, the system recognizes a slot as empty or occupied based on training set which is embedded in raspberry-pi using artificial intelligence. If the vehicle is parked for more time than what it was booked for, extra money has to be paid at the exit.

    Drawbacks of existing system is that until the recent times, dijkstras algorithm is used to find shortest path for parking the vehicle efficiently but its main disadvantage is that it does blind search hence a lot of time is wasted while processing. This leads to wastage of fuel energy and creates chaos if the user is unsure of the right path to be taken. To overcome this disadvantage, an efficient best first greedy algorithm is used which is proved to be faster and more accurate in finding the shortest path for traversal.

    Computation of function is as follows:


    where g(n) is the distance from the start node(entry point) to node n and h(n) is the distance from node n to destination node(exit point).Use of h(n) is through Euclidean distance formula:

    Distance=(( ) +( )) —————— (2)

    Where (a1,b1) are the coordinates of current node and

    (a2,b2) are the coordinates of destination node. Design approach to this system is as follows:

      1. Function Models:

        1. Optimized path recommendation unit: It communicates with the CPU (raspberry-pi) and recommends the best routes to the driver considering the obstacles and congestion.

        2. Real-time vehicle locator using GPS : The locator interacts with the processing unit (raspberry-pi) and determines the exact location of vehicle and sends the same information to the user.

      2. Optimal Pat Finding Algorithm:

    1. Set the start and end positions of vehicles noted by the RFID reader at the check-in and allotted slot (destination) respectively. Google maps will recommend the shortest route based on the implementation of algorithm.

    2. Compute the best route using the path-finding algorithm

    3. Determine whether the suggested route has any obstacles or not.

    4. If the route does not have obstacle or congestion, then it can follow the recommended best route.

    5. If the route has any obstacle, then the next optimal route is determined by the algorithm.

    6. Drive to end.

    Fig 3. Flowchart of optimal path induction.


    In this paper, an efficient path searching algorithm is proposed. Some of the advantages of using it are as follows:

    1. Path is smoothened because of combining all the path- points which ultimately results in faster speed.

    2. It initially finds the collision at every unit of distance, examines first and executes later.

    3. It considers both stationary and movable obstacles. The user gets the path direction of route to be traversed through GPS from a mobile application. Smart parking system using this algorithm for path optimization helps the driver to save time, fuel and increase the parking efficiency.


[1] Muftah Fraifer, Mikael Fernström, Smart Car Parking System Prototype Utilizing CCTV Nodes , 2015.

[2] Thanh nam pham, ming-fong tsai, duc binh nguyen,chyi- ren dow, and der-jiunn deng " A Cloud-Based Smart-Parking System Based on Internet-of-Things Technologies " ,2016

[3] Mohammed Y Aalsalem, Wazir Zada Khan CampusSense A Smart Vehicle Parking Monitoring and Management System using ANPR Cameras an d Android Phones,2016

[4] Abhirup Khanna, Rishi Anand IoT based Smart Parking System,2016

[5] Mahendra B M , Dr Savita Sonoli , Nagaraj bhat, Raju, Raghu T,IoT Based Sensor Enabled Smart Car Parking for Advanced Driver Assistance System,2017

[6] Giuseppe Amato, Fabio Carrara, Fabrizio Falchi, Claudio Gennaroand Claudio VairoISTI-CNR, via G. Moruzzi 1, Pisa, Italy

,Car Parking Occupancy Detection Using Smart Camera Networks

and Deep Learning,2017

[7] Oluwatimilehin Olumolade, Haowen Jiang, Alexander Forde, Yazeed Almania, Barjas Alsahli,Yu Zhang, Md Anam Mahmud, Ahmed Abdelgawad, Kumar Yelamarthi The Design and Implementation of a Smart Parking Meter for Internet of Vehicle (IoV),2017

[8] Chihhsiong Shih, Zhaolong Liang ,The development and simulation of a smart parking guidance system,2017

[9] Yujin, Ge Xiaoxue, Optimal Route Planning of Parking Lot Based on Dijkstra Algorithm,2017

Leave a Reply