Path planning with D* lite algorithm for fully-automated and multi-story parking

Within the scope of the thesis, a software framework developed to dynamically manage multiple and simultaneous parking and retrieval requests in fully automatic car parks is presented. D* Lite, A* and UCS algorithms with heuristic search feature are combined under a single software framework as appropriate. The designed parking lot consists of a series of rectangular parking cells with as well as blank cells that are separated to form elevator, loading area, entrance, exit and passageways. All parking cells in the parking lot storage topology is conceived to be on moveable carts. There are no driving lanes other than the separated blank cells. It is also assumed that the entire floor is full except for the blank cells that will create temporary passageways in the simulation. The number of blank cells have to be determined in a way that will both maximize storage capacity and respond to parking requests in real time. The thesis also proposes storage strategies that will facilitate the completion of the process by following a path that is as close as possible to the optimal or shortest path in the existing parking lot layout. The simulation results show that the automatic parking system presented in this thesis is feasible and practical. The actual path lengths measured through the number of movements per request is close to the computed shortest path length. This means the system provides a nearly optimal path for each request. The system provides a quick response during the path planning process even in the presence of tens of concurrent storage and retrieval requests in real-time environments. The simulations have shown that the set of algorithms developed for fully automatic parking lots can meet tens of real-time simultaneous parking and retrieving demands with manageable computing resources under real-life scenarios.