PRE2019 4 Group8

Towards a Design and Model of a Parking Assistant Robotic System

Group Members

Name	Student ID
Sietse Backx	1255924	s.backx@student.tue.nl
Rien Boonstoppel	0946480	d.j.boonstoppel@student.tue.nl
Luc Geurts	1237117	l.p.a.geurts@student.tue.nl
Mandy Grooters	1236053	m.grooters1@student.tue.nl
Tar van Kieken	1244433	t.m.k.v.krieken@student.tue.nl

Introduction

Visiting the airport usually results in a lot of stress already. You need to take your clumsy luggage through the whole airport, wait a lot in different lines and after that sit in a too small chair in the plane before again entering different waiting lines at your destination. However, it can get worse by trying to park your car in what seems to be a never-ending, saturated parking lot on the airport. Parking demand often does not meet the supply and in combination with a shortage in parking staff, does this result in leaving drivers with frustration.

A survey performed by the Airports Council International has revealed that up to 50% of the total revenue of an airport is generated by non aeronautical services, including parking. For example in Denver, 13% of the total revenfrom the parking services and in Minnesota even 30%. This also includes the rental of vehicles for people on their holiday or business trips. This shows that parking is a big and important part of the revenue of airports and that making parking more efficient and attractive for users, could have a big positive impact on the income of the airport.

When opening a parking lot for an airport, there are several key aspects to take into account with regard to transportation and vehicle placement or traffic management in general. There is often not a lot of road capacity at the airport , which makes it hard to build a big parking lot. Also are the costs a big and important factor for the building and maintaining of a parking lot, because a parking lot is a big investment of an airport. A solution for this problem is to use more public transport as a way to get to the airport. Schiphol for example has his own train station under the airport, to encourage people to get to the airport with the train. If all these measures still lead to congestion, a new solution must be found.

Analogously with airport parking lots, in large cities, parking is also a considerable problem. Nearly 30% of traffic congestion in cities is caused by drivers looking for a parking spot . Designing a parking system such that drivers can find a parking faster is therefore essential. Common solutions involve a LED system to indicate free and occupied parking spaces, however, these solutions do not control traffic flow. Another option which does take into account traffic flow is automatic parking spot assignment. Automatic parking assignment can compute optimal routes taking into account lot occupancy, travel distance, conflict avoidance and walking distance . Nonetheless, this solution is limited to mobile phone use.

Objectives

Subject

A robotic parking assistant which helps drivers to find a parking spot in a parking lot of an airport (in this case Schiphol) and simultaneously optimizes traffic flow for faster parking.

Problem Statement

In summary, the key issues to resolve are the enormous rise in demand of better parking conditions in parking lots. These issues result in congestion and frustration of drivers due to the delay suffered from finding a parking space. This project researches the possibility to improve the parking experience on parking lots. Focus is on parking lots with a proper road surface, and a limited number of entrances/exit. These constraints exclude temporary parking lots on meadows, or general parking spots along a road. In addition to the research, we design a partial solution for the issue by making a design of the parts of the system that the user would interface with, and software to manage the parking lot plus a simple simulation.

RPC's

In order to investigate possible solutions, requirements, preferences and constraints have to be established.

Requirements

• The system should be able to know in which path and row in the parking lot it is located at any moment in time.
• The system should be able to operate autonomously.
• The system should regulate traffic flow for both entrance and exit of the parking lot, taking into account the total capacity of the parking lot.
• The system should detect if cars are parked on the wrong parking spot or more than 20 cm over the parking lines and take this into account in the determination of free parking spots.
• The system should not come closer than 0.7 meters to the secondary users
• The system should be able to detect when the secondary user needs a parking spot for disabled or older people.
• The system should be able to communicate with the secondary users in a clear way where they need to go for their designated parking spot (97% of the people should understand the communication).
• The system should have a help option to solve parking issues and if needed contact the primary user to help the secondary users
• The system should handle cars up to 5 meters in length and up to 1.8 meters in width.
• The system should be waterproof.

Preferences

• The system should be able to handle payments at the exit.
• The system should look as humanly as possible to decrease the distance where the secondary user feels an invasion of personal space.
• The system should be able to read the licence plate of the cars.
• The system should be able to guide the user to its car when they forgot their parking space, based on the license plate.
• The system should be able to investigate the parking layout by itself.
• The system should give users the opportunity to state their parking preferences and handle those accordingly.
• The system should be able to instruct the driver to park their vehicle properly if it is misplaced.
• The system should have a feedback option.
• The system should have an emergency option.
• The system should be able to fill a parking lot with cars in a shorter time than current valet-parking options.
• The system should be able to measure the length, width and height of the incoming car, in order to know whether it fits in certain parking spaces.
• The system should be cheaper to exploit than current valet-parking options over a span of 10 years.

Constraints

• The system should be ground-based.
• The parking lot has clear entrance(s) and exit(s) which can be regulated and entrance.
• A parking space has the following dimensions in the Netherlands.
  • 5 meter length by 2.4 meter width, when perpendicular parking.
  • 6 meter length by 2.5 meter width, when parallel parking.
  • 6 meter length by 3.5 meter width for the disabled parking space when parallel parking.
  • 5 meter length by 3.5 meter width for the disabled parking space when perpendicular parking.

Airport

There is chosen for the focus of the parking robot on an airport parking lot. One property of such kind of parking lot, is that there will be cars entering and leaving the parking lot the whole day. This is different from things like the amusement parks, where you have a spike in people entering on the opening time and a spike of people leaving at the closing time. This results in that our robot needs to be good in the managing of the available parking spots in the lot. In an amusement park or event situation is it easier to just fill the parking spots from the entrance until the back. However, in the airport parking lot are there continuously people leaving and entering, which makes it more of a challenge for the software to choose the best parking spot available at any time. Another parking lot, for example at a mall, could also be chosen for our project. This would also have the challenge of people continuously leaving and entering. There is however chosen for this application place, because there are more user preferences in an airport parking space. There are people with a lot of luggage, who want to park close to an elevator, people who want to park close to the entrance, people who only want to drop a person off and so on. This results in that we need to focus more on the users and thus more on the preferences of the car drivers. This must be incorporated in the software and result in a bigger challenge for us.

Deliverables

The goal of the project is to deliver a design for the parking robot. This design is dependent on the needs of the users, the requirements we made earlier and the working space, which is in this case a parking lot on an airport, like Schiphol. Furthermore do we want to develop a software, which recognizes parking spaces and gives the best parking space dependent on the preferences to the user. We will also finish this wiki page in such a way that it shows the complete progress that we made during this project. Lastly will we make a presentation video, which shows the steps that we made in this project.

User, Society and Enterprise

There are different users which will use the parking robot. It is important for the design of the hardware and software to take the needs of these different users into account. This chapter lists the different users with their needs and researches the best way for the interaction of our robot with the users.

Users of the Parking Robot

The primary users of the parking robot are companies that are dealing with large parking lots. Such as airports. These companies want to improve the experience of their visitors by avoiding parking problems. The parking robot will significantly decrease the waiting times for a parking spot and thus increase the overall experience of the visitors.

The secondary users are the visitors of the airport that are directly interacting with the parking robot to find a parking spot. The parking robot can quickly guide them to a parking spot. Without the parking robot, visitors would have to wait longer which adds stress and frustration to their day which will decrease their experience . These secondary users can be divided into different categories which are again assigned to their designated parking areas. The primary users can assign these specific areas to their preferences and it depends on their targeted audience. As an example, one can have a different parking area for disabled people, an area for the elderly and an area for large families. These groups all have different preferences with respect to where they want to park. To elaborate on this, the elderly for example, they want to have parking spaces closer to their destination which will provide them with a shorter walking distance. Disabled people will also want their designated parking spots close to their final destination and extra room for parking as they sometimes are dependent on wheelchairs or other devices. They may also need quick access to wheelchair ramps, restrooms and special ticketing services. As for the family category, they don’t need any special preferences as they can just be used to fill up the remaining parking spots when all the others have been assigned.

For society, the parking robot can have great improvement opportunities. The parking robot will be more efficient than the current traffic controllers, which will improve the traffic flow around the parking lots. Consequently, the traffic flow on high- and motorways around the parking spot will improve. Therefore, people that do not visit the airport will not experience any delay in their travel due to this effect. Furthermore, congestion increases fuel consumption, environmental pollution and traffic accidents. So the parking robot will have a decreasing effect on these matters too.

From an enterprise perspective, multiple groups can take advantage of the parking robot. First, the organization of airport parking garages. They don’t have to deploy traffic controllers anymore. Which eventually could decrease their overall costs. Secondly, the research that will be done is interesting for the development of other robots. The navigation and communication technique used in the parking robot could be applied in other areas as well. When the parking robot will be developed on a larger scale, robot companies have to produce more robots than they do now, which will eventually decrease the cost per robot. The profit companies make, because of the enhanced traffic flow caused by the parking robot, could be used to do more research on parking robots or robots who use this navigation and communication technology in general. Such can lead to the continuous improvement of the used techniques.

When summarized, we can identify the following user groups:

• Deployer companies: The companies deploying the system
• Drivers: The people that need to park their car
  • Disabled people: People that need to find a parking spot suitable for people with physical disabilities
  • Infirm people: People that have walking difficulties
  • Bad drivers: People that have more difficulty with driving and parking
  • Average people: People that don't have special needs of any type

Enquête (draft)

A survey was done to investigate the secondary users’ opinion about communication with the parking robot. The goal was to determine which form of user-robot interaction is preferred. This was done by asking questions about the way of communication between the robot and the secondary users and about what people would do in situations that may occur. Such as what they would do when they don’t understand the robot. This data is used to determine the way our robot will communicate with the secondary users.

A total of 175 people have filled in the survey. The largest part of the people (around 60%) are in the age group of 18-30 years old. The other 40% consist of mostly people between 31-50 years old (25%) and people between 51 and 70 years old (15%). Furthermore we asked about the education, if the person has a driver license and if they have a technical background. The education was found out to be quite split between high school (28%), MBO (19%), University (26%) and HBO (25%). Over 85% had a driver licence and over 60% has a technical background, which can be a technical study or working in a technical company.

We also asked about the affinity with robots. Because when the affinity is rather high or low, this may influence their opinion about the parking robot. And with this data the the participants general view on robots can be compared and connected with their view on the parking robot. People could rate their affinity with robots with a grade between 1-10. Where 1 means no affinity at all and 10 means that they have a lot of affinity with robot. The average grade people gave was a 5.7.

To determine the participants opinion about the ways of communication, several scenarios were presented in which they could choose their preferred way of communication. For example, people could choose how they want to be greeted by the robot and how they would like to communicate any special preferences they may have.

Touchscreens/speech Despite the coronavirus, 60 % of the participants preferred to communicate their preferences with the use of a touchscreen. Only 4% of the participants would like the robot to communicate via speech at which they have to react via speech. So, there is concluded that the parking robot will communicate with the secondary users by using a touchscreen. But it is necessary to think about the cleaning of the places on the robot that are touched by users.

Stukje rien

Text/icons

Furthermore, some questions were asked about the way that the parking place should be communicated in the best and clearest way to the driver. There is chosen for the options of icons, text or icons with text to communicate with the driver. We also gave the option of an attached arm to the robot, which shows the direction where the driver needs to go. From these questions we found out that most of the participants want to have text, sometimes accompanied with icons, because they think that this is the most clear method. The only option in which they did give this answer, was with the arrow icon, which shows how you need to drive in the parking lot on the way to your parking space. The conclusion from this is that it is only chosen for non-ambiguous emojis. The arrow emoji is in this situation the only emoji from which it is immediately very clear what it means without more explanation with text. From this data we decided that we want to use arrow icons for the guiding of the driver through the parking lot and when the user arrives at the parking space, but we want to use a combination of icons and text at the arrival and at the departure.

Preferences

In the beginning of the survey was asked if the user would want to give preferences to the parking robot when they enter the parking lot. Over 75% of the users did want to communicate their preferences to the robot, if that means that they get a better parking spot that takes their preferences into account. When asked what preferences the users have in the survey, it was found that 63% of the people would like the parking spot closest to the entrance. There were also a lot of people who wanted to have the largest parking space or the easiest driving route. There were also some preferences added, such as the parking space with the easiest way out of the parking lot and the safest way to park their car. From these results can be concluded that the secondary users indeed have preferences with respect to their parking spot. Hence, the option that allows the secondary users to communicate their preferences will be included in the parking robot. The preferences of the users will be communicated with the robot via a touchscreen. In the parking lot are parking spots that are designated to disabled people.To make use of these parking spots one needs a card for disabled parking. Currently, there is checked if people that park at the disabled parking spot have a disabled parking card in their window. When someone communicates with the robot that they prefer a parking spot for disabled people, the robot will scan their disabled parking card to check if they are allowed to. After this the parking robot will guide the secondary user to their parking spot. As an addition, the parking robot will have the option to remember the preferences connected to each license plate. Such that people who visit the parking lot multiple times, can be guided to their parking spot even faster. When someone enters or leaves the parking lot they will get the question if they the robot to remember their preferences. privacy

Robot die corrigeert

When someone is not parked neatly this could make that the parking lot cannot be used completely or that it is harder to park for other people. The participants were informed about this and were told that the parking robot can correct someone when they did not park neatly to solve this problem. The participants were first asked to rate how they would feel about a robot correcting someone in general with a grade between 1-10. Where 1 means that they do not like that idea at all and 10 means that they really like the idea. After this they were asked to rate how they would feel if the robot would correct them. People rated correcting someone in general with an average of 7.0 and correction themselves with an average of 6.3. From this can be concluded that people like the idea of the robot correcting someone and this will be implemented in our robot. The robot can correct someone in several ways, the robot can display a text, show an animation of a car that parks again, or use augmented reality to show where the car is not parked correctly. The two options that were chosen the most were augmented reality (36%) and text (35%). Only 11% would like an animation that shows a car that parks again. There is chosen to combine text and augmented reality to give the clearest instructions to the drivers. When someone does not react to the robot the robot will try once again by showing the text and augmented reality footage. When the driver still doesn’t park again the parking robot will registrate how the car is parked and will take this into account when assigning parking spots to other cars. When someone parked their car a large part across the line, the robot will check if cars are still able to park next to that car. And if necessary, the robot will only assign the partly occupied parking spot to a smaller car or registrate that no car will fit in there. Most importantly, the robot should always be kind to the drivers, and never be offensive or pushy, even when someone is not following the directions of the robot. wanneer moet de robot stoppen met corrigeren? hoe willen we het laten zien want mensen in de auto zien het niet?

Niet snapt

It could happen that someone does not understand the robot and there is asked how people would react in such a situation. The two options that were chosen the most were that the person would drive off and just find a parking spot themself (50%) and that the driver would stand still and wait on clearer instructions (40%). The first option will not be a big problem for the robot, only that the robot does need to know where the user eventually parks such that the system will not see this as a free parking spot. The second option can be a big problem for the parking lot, because it obstructs the traffic flow when someone would stand still in the middle of the parking lot. The robot should be able to notice when someone is not understanding the directions and is standing still. When this happens the robot will show the directions once again. When after ….. times the driver is still standing still, the robot will show a screen that says the driver can search for a parking spot on their own. After this the robot should register their chosen parking spot. But there needs to be made sure that the communication between the robot and the user is very clear such that the previous mentioned situations will not occur often.

Parkeerplek terugvinden

The parking robot could help people with finding back their parking spot by remembering their license plate. The participants were asked if they would like this feature. Most of the participants (79%) think this feature is useful. The other 21% has some objections towards this feature such as a lack of privacy or not wanting to remember their license plates themselves. The robot will remember the license plates of cars to keep track of how many cars are parked in the parking lot. People are not required to use this feature, so not remembering their license plates won’t be a problem.

When someone wishes to make use of this feature, one can walk to the robot and hoe weet de robot dat je wat wil? staat er op het beginscherm iets van parkeerplek terugvinden? ……..

Then the robot will slowly guide them to their car. Taking into account the walking speed. Of plattegrond/rijnummer enz laten zien?

Human Robot Interaction

Touchscreens

Because of the current state of the world around the coronavirus we choose not to use touchscreens. Although it is not yet scientifically proven that this virus is spreading over surfaces, it is widely proven that touchscreens are a possible contamination hazard. So below is elaborated on three other possible solutions for the interaction with the proposed system.

Speech based

This is the most promising solution in my opinion. The voice is the most prominent and the primary method of communication among the human beings. With speech humans can also communicate with robotic systems. However, the possibility that the proposed system is going to be used in busy and noisy environments is quite high. So there need to be some sort of enhancement over a simple microphone. In 1990 already the research on the use of microphone arrays in order to enhance speech recognition based on beamforming. In recent days, Google has made huge improvements with their Cocktail Party challenge. With only a single audio track but with added video feed, they were able to completely isolate voices. So possibly by combining those both solutions will lead to a great performance on speech recognition in busy and noisy environments.

Gestures based

The second possible way for interaction with our robotic system is gesture based. Some research is done on the use of gestures for the interaction. For example by using cameras or a Kinect to view gestures of the secondary users. However, this can be difficult because of the restricted space a driver has behind the wheel. Maybe using hand signals something is possible.

Touchless display

A different, more experimental approach is more like a classic touchscreen. However, without touching the actual screen. A touchless display is developed which can sense local variations of the humidity in the air. When you point a finger, local air humidity changes, which can be translated tot spatial information using those ultrasensitive humidity sensors. The simplicity of the interaction via a touchscreen-like display is already widely acknowledged, so that is a advantage. But it is a very experimental display so its reliability has yet to be proven.

The partial solutions to driver communication.

Primary users

In the previous section, the different types of users were elaborated. In this section the needs of the primary user are discussed.

The primary users are the companies which own and manage the parking lot. In order for them to invest in the parking assistant robot, the robot needs to be more beneficial than the current system in several aspects. The first aspect is cost. If the robotic system offers similar benefits for a smaller price, companies might consider to buy the system. Another scenario might be that the robotic system is slightly more expensive, but offers features to increase parking lot profits. An example of this could be that lots which are close to the exits are made premium parking lots. The secondary user could specify to the robot that he/she desires a premium parking lot with additional charge. Another aspect is the amount of parking lots available. Currently, parking garages count the arriving and exiting cars at the barrier. This method is flawed as some drivers rapidly follow after the previous driver. On top of that, double parking is not accounted for. With the robot, a more accurate count can be kept of the available spaces so that a better indication could be given to arriving customers. Additionally, parking lots for regular customers with a subscription could also be used if the customers are not using the lots. The system could message these users. If an incentive is given to these users for offering their space, such as a discount, both the primary user and secondary user could significantly profit. Finally, the most important factor is safety. The primary user will not invest if the robot endangers users.

Secondary users

Draft resultaten survey

175 respondenten

Korte analyse resultaten:

• Begroeting / afscheid nemen: het liefst emoji/tekst of alleen tekst
• 78.3% vindt het fijn om preferences door te geven

Meest voorkomende preferences:

• Dichtbij de uitgang
• Grootste parkeerplaats
• Makkelijkste rij route

We waren vergeten te benoemen dat invalidenplekken sowieso toegewezen worden.

Interactie met robot

• 60.6% kiest voor touchscreen
• 35.4% vorm van spraak

• Begeleiden naar parkeerplek:
  • 53.7% kiest voor symbolen
  • 37.3% kiest voor tekst

• Als iemand de robot niet snapt:
  • 50.3% zoekt zelf een plek
  • 40% blijft stil staan

• 54.3% wil naar parkeerplek gebracht worden door icoontjes
• 33.7% door tekst

• Mensen vinden het over het algemeen een goed idee dat de robot mensen corrigeert. Maar 7.4% wil niet gecorrigeerd worden.
• Gecorrigeerd worden door tekst of videobeelden. Combinatie van maken?
• welke leeftijd heeft meer moeite met het corrigeren van parkeren? -> analyseren

• 78.9% zou graag geholpen willen worden met auto terugvinden. Maar het kan dat mensen het niet willen ivm privacy. Misschien bij parkeren mensen laten kiezen of ze willen dat de robot het onthoud?

Losse opmerkingen vanuit enquete

• Privacy issues
• Op te lossen via slimme navigatie systemen( -> iets voor in de toekomst)
• Tekst en iconen combineren
  • Nadenken over duidelijke iconen
  • Als het goed geparkeerd is, een duim laten zien.
• Gebruik van knoppen in plaats van touchscreen
  • makkelijker schoon te maken?
• Verschillende talen? Bij op het beginscherm zetten?
  • Let op zware accenten bijv
• Als parkeerplek geselecteerd is, deze laten zien, en aangeven hoever het rijden is
• Denk na over accessibility options voor gehandicapten
• Vaste borden en begeleidingsverlichting
  • Toegevoegde waarde met rijdende robot
• Herinner mijn voorkeuren op basis van parkeerplaats
• Hoeveel van die dingen heb je nodig?

Software

The first deliverable is the software which can be used in the parking robot to determine the best free parking space in the parking lot dependent on the preferences of the users. This software is developed in this chapter of the wiki page.

State-of-the-art

A lot of technologies are produced for the tracking of the availability of parking spaces. The simplest and first technology for tracking the availability, is the tracking of the total capacity of the parking lot and the amount of cars which enter and leave the space. This is already used in a lot parking spaces of malls, theme parks or other parking lots with a clear enter and leave point.

The second method is to check if there is a vehicle on a parking spot with a detection unit on every parking unit itself. This detection unit can for example be an induction coil, ultrasonic sensor, infrared sensor, pressure sensor or a microwave sensor. The information of all detection devices is then gathered in one management system, to check the overall availability of the parking lot. The individual spots can be characterized by giving a value of 1 or 0 in the system or by setting them as “AVAILABLE” or “OCCUPIED” on the place where it is shown to the user.

Another method for the tracking of free parking spaces, is to use a given three-dimensional model of the parking lot. A capture device can then be used to represent an image of the parking lot, which can be compared with the three-dimensional model of an empty parking lot. From this comparison of the two three-dimensional models, the availability of parking spots can be determined and translated back to the user.

The parking lot can also be divided in different slots of a certain number of parking spaces. For example, ten parking spaces can be divided into two slots of five parking spaces. The GPS of cars can be used to track in which parking slot the car is located. From this information can be determined how many parking spaces are left in each parking slot and can the next car be directed to the parking slot with available parking spaces.

All the previous systems use some kind of tracking method to determine the availability of the parking spaces. Another method is predicting the availability of parking spaces by looking at patterns in old data. With this method is giving a precise number of available parking spaces not possible, due to the accuracy of long term predictions, the other parking lots in the area and the user behavior. However, if the accuracy of this method is high enough, can it still result in good approximations of the vacant places on parking lots.

Architecture

We wrote software which can be used as 'the brain' of the parking lot. This software is able to run on a local server at a parking lot, and all robots are able to communicate with it over an internet connection. This software is written in TypeScript and runs in NodeJS. It uses Socket.io in order to facilitate symmetric communication. In addition, a front-end web application is provided through the server, in order to show a simple simulation of the parking lot. This was added to show the capabilities of the system, without having to create the physical robots. This application is also written in TypeScript and uses the following important libraries:

• React for view creation
• Model-React for data management
• PixiJS for dynamic graphics
• React-Pixi-Fiber to use PixiJS with React
• Fluent UI for UI components

Algorithms

The main goal of the software is to track what parking spaces are available, and to find appropriate parking spaces for users. To achieve this, the owner of the parking lot has to provide a graph that represents the parking lot. All valid vehicle paths, but also pedestrian paths will have to be present in this graph. Special nodes also have to be marked, which includes:

• Parking spots
• Vehicle entrances
• Vehicle exits
• Pedestrian entrances
• Pedestrian exits

Each of the nodes also contains spatial data for where it's located in the parking lot.

Below is an example graph, where colored nodes have the following meaning:

• Light green: Vehicle entrance
• Dark green: Pedestrian entrance/exit
• Light red: Vehicle exit
• Purple: Parking spots

Simple parking lot graph

Search algorithm

Dijkstra's algorithm together with a min-heap is used to perform the search. This algorithm can find the cheapest path between two nodes in a graph, in an efficient manner. It computes the cheapest path from a start node to any node in the graph. This by itself is not sufficient for our search however, since we aren't just interested in the distance between two points. We want to consider a number of variables, including:

• Total driving distance from entrance to exit
• Total walking distance from parking spot to an pedestrian exit
• Total walking distance from a pedestrian entrance to the parking spot (in case there are seperate entrances and exits)
• Difficulty to get to a parking spot (based on E.G. number of turns required)

In order to consider all these aspects, graph transformations are used to obtain graphs that Dijkstra's algorithm can be used on.

Graph transformations

Given the graph of the parking lot, the software will create so called 'search graphs'. These are graphs where the physical location of nodes is abstracted away. These do not represent the parking lot in a physical manor anymore, but all relevant information to determine the ideal spot is retained. This relevant information is encoded in the form of edge weights, which can be used to determine costs from one node to another. This way the cost to get from the entrance to a parking spot can still be determined, without having to consider physical location. Each node also contains a reference to the node it was created from, in order to translate path found in the search graph back to a physical route. The system creates 3 different search graphs, which are all used in the final search that combines the information:

• Pedestrian entrance to spot graph
• Pedestrian exit to spot graph
• Vehicle entrance through spot to exit graph

These graphs are only created once when the system starts up, therefor efficiency of creating these isn't a major concern.

Pedestrian entrance to spot graph

This graph is a simple graph that uses Euclidean distance as weights on all edges, and only retains nodes and edges that may be traversed by pedestrians. This graph therefor allows the distance between a given entrance and any parking spot to be determined

Pedestrian exit to spot graph

Similar to the other pedestrian graph, this graph uses Euclidean distance as weights on all edges, and only retains nodes and edges that may be traversed by pedestrians. In addition, it reverses all edges, such that if you were only allowed to walk towards the exit over a path, you are now only allowed to walk away from the exit over said path. This graph therefor allows the distance between a given exit and any parking spot to be determined

Vehicle entrance through spot to exit graph

This graph only retains edges traversable by vehicles. It first creates two instances of the graph, where the first doesn't contain any vehicle exits, and the second doesn't contain any vehicle entrances. Then it connects the two graph through the parking spots. An example illustration is provided below.

Spot routing

This way we can search for the cheapest path from a vehicle entrance to a vehicle exit, which has to pass through at least one parking spot. In this graph, all edge weights are simply the euclidian distance between the nodes.

A second transformation is applied to this graph, which introduces costs for each turn taken. Every node in the original graph is replaced by the product of the set of incoming and exiting edges. This way we can add an edge between any pair of incoming and exiting edges, and give it a weight relative to the turn that's required to make this transition. An example illustration is provided below.

Turning cost transformation

Using this graph we can find the spot that requires the minimal distance to be driven, and fewest turns to be taken.

Graph search

In the search algorithm, the information of all 3 graphs is combined. First a search is executed on both pedestrian graphs in order to determine the cost to reach any spot by foot. In this search a 'walk cost' is used to multiply the distances with in order to consider user preferences.

Then a search is done in the vehicle graph. In this search any turn edge is multiplied with a 'turn cost' to once again consider user preferences. When the search algorithm encounters an edge through a parking spot, the walking cost calculated in the previous spot is provided. In addition an infinite cost is provided in case the parking spot is already taken. The result of this search will is the cheapest path from the entrance to the exit of the parking lot, passing through a parking spot. The parking spot is extracted from this path in order to retrieve the pedestrian paths to and from this spot as well, and all paths are returned as the search result.

The costly graph transformations are only executed once, and per search we only have to use Dijkstra's simple and efficient search algorithm a couple of times.

Results

The simulation can be viewed at herokuapp. The software is running on a centralized server. Thus any changes made, such as parking a car, are visible to anyone visiting the site. The source-code of the software will be visible in the future

Hardware

The second thing that we want to deliver is a design of the parking robot. This design is developed in this chapter.

State-of-the-art

If the information of the available parking places is measured, it is important that the system can choose the best possible parking spot for the vehicle. There are different performance measures for the best parking spot, but the most used ones are a combination of that the time riding to the parking spot and the time walking from the parking spot to the destination are minimal.

When the optimal parking spot is chosen, can this be passed to the user in different ways. The first one is to show the route to the parking spot on the dashboard of the vehicle. A lot of cars nowadays have GPS on the dashboard and this can be used to show the information of the parking spots. This results in that there needs to be a continuous information flow between the vehicle and the availability of the parking space.

This can however also be done with predicted information of the availability of the parking spaces. This information can be given to the GPS of the vehicle, such that the route to the predicted available spot is displayed on the dashboard.

A lot of the times, employers are deployed to guide the vehicles to the empty parking spots. This can be seen on parking lots for places like festival, amusement parks and museums. This can be replaced by robotic solutions. Signs can be set on the ground with information on where the vehicle needs to go for the empty parking spot. For example a sign with an arrow or an cross can be used to show in a simple way for the user, which way he needs to follow.

The employers can also be replaced by robotic vehicles that lead the vehicle to the best parking spot. These robots can fully ride the way of the beginning of the parking lot to the parking spot, or can be used as robotic employers, by going to the crossings and then showing the right way to the user in the vehicle.

Concepts

Obstacle avoidance and parking availability

In order for the system to avoid parked cars and guide drivers safely to their designated parking spot, the system should be able to observe its environment and determine its position. To be able to this, two types of sensors can be used, namely: dead reckoning sensors and environmental sensors. Dead reckoning sensor operate by integrating sensor data over time to determine the vehicles position. Environmental sensors are used to gather information about the vehicles surroundings.

The first sensor option is to use cameras which can observe in 360° short or long range. These cameras can be placed either on top of the vehicle, on the sides of the vehicles or externally placed (see figure below). The key application for this cameras is to recognize objects. Some tasks such as traffic light identification is only possible with the use of cameras. However, because of the great amount of pixels, camera data processing can be intensive. On top of that, camera quality is susceptible to environmental conditions such as rain, fog or snow.

Radar can also be used either at short or long range. Different objects reflect the radio waves differently. The advantage of using radar is that positional and velocity data can be acquired simultaneously. On top of that, radars are impervious to weather conditions. Despite, radar acquired data yields low resolution and a 2D image.

Lidar uses light to receive information about distances between objects. Lidar is used for short range applications. It is used to obtain position and geometry of an object. If multiple Emitter and receiver sets are placed on the vehicle, Lidar can be used to create a 3D image of the environment. Next to that, because dark and light objects reflect light at a different intensity, Lidar can be used to detect road markings. A disadvantage is that Lidar data can be affected by the weather.

Ultrasonic sensors are short range and unaffected by weather conditions. Currently, ultrasonic sensors are used for parking assist.

GPS can be used to determine the vehicle position globally. GPS, however, is not enough to determine the position with great accuracy, as GPS can only obtain an objects position with 1-2 m accuracy.

In general, all of the sensors considered above have pros and cons. Hence, these sensors are often used in combination in self-driving vehicles.

The partial solutions to obstacle avoidance and parking availability.

Vehicle motion

Another crucial aspect of the parking assistant robot is motion. The robot should both be able to operate on asphalt and rough terrain. Therefore, a solution must be found to allow smooth operation in both environments.

The first option is to use large wheels with a thick profile. If the wheels are independently propelled and sprung, the vehicle will even be able to have grip in a muddy and bumpy environment. Another option is to use tracks. Tracks are used in the most inaccessible terrains. However, tracks are not as suitable for use on asphalt. Another option is to use legs. The advantage of legs as that they can move the vehicle in nearly all environments. Nonetheless, legs often require complex mechanical actuating systems (see figure below).

Additionally, steering must be considered. This can either be done by rotating left and right wheels or tracks at different speeds or by turning the front or back wheels.

The partial solutions to vehicle motion.

Integrated solutions

Requirement: able to turn on its place Preference: as small footprint as possible

Solution 1

A two wheel based self-stabilizing robot – like a segway

• Display on eye level
• Sensors on top
• Weight distribution on top en bottom in order to maintain balance

Pros

• Small wheelbase, able to navigate to relative small places
• Agile
• Ability to keep itself upright after perturbation

Cons

• Possibly less stable
• Possibly dangerous movements when trying to keep itself upright

A two wheel based self-stabilizing robot.

Solution 2

A four wheel based robot – two powered wheels, two caster wheels

• Display on eye level
• Sensors on top
• Weight distribution on bottom in order to lower center of mass

Pros

• Stable from itself

Cons

• Less ability to react to perturbations to keep itself upright
• Because of the dimensions of the robot (way taller then wide) not that stable
• Bigger footprint then two wheel based

A four wheel based robot – two powered wheels, two caster wheels.

Solution 3

A two wheel based robot, with added extra control wheel. The arm of this of this extra control wheel is sprung and shock absorbing, the wheel can be a fixed one or a castor wheel and is in normal use not touching the ground.

Pros

• Same as solution 1

Cons

• More stable then solution 1
• Because of the added control wheel smaller correction suffice to keep upright, so it is less dangerous

A two wheel based robot, with added extra control wheel.

Solution 4

With the previous two wheel based solutions, stability is a key issue. Also, with a narrow base four wheel base robot, tipping over is a risk. Therefore, this concept has four wheels with a larger width and length to reduce this risk. The advantage of the two wheel concepts is the maneuverability. In order to have the same maneuverability, four omnidirectional wheels are used to allow the robot to rotate at its position.

A four wheel based robot, with omnidirectional wheels.

Detailing

Approximations

In order to find appropriate components for the robot, estimations have to be made. Therefore, in this section some global parameters are established.

In the figure at solution 4, the current concept is depicted. This figure gives a course overview of all the components that need to be present in the final design. The final design needs to have the following components; a screen or light display for interaction with the secondary user, wheels, suspension, actuators, sensors, a computer, a battery pack and additional lighting.

With regard to mass, the led screen of the robot has an approximate mass of 20 kg. Next to that, the four omnidirectional Mecanum wheels of 254 mm diameter have a combined mass of 12 kg . Concerning the sensors, these consist of Lidars, camera's and radar. The weight of these sensors combined is expected to be 1 kg. In order to compute the algorithm, hardware is needed. This hardware is guessed to be 10 kg.

All components have to be put together in a structure. This structure needs to be rigid and needs to resist minor crash loads. The structure combined with the spring dampers is expected to weigh 20 kg.

The wheels have to be individually propelled with actuators. These actuators need to accelerate and decelerate (using dc injection braking). The robot will travel at an average velocity of 15 km/h in the parking lot. If the robot has a maximum speed of 30 km/h and accelerates at a maximum acceleration of 2 m/s^2, for a robot weighing 100 kg, a force of 200 N is needed. Given a wheel diameter of 254 mm, the required torque is equal to 25 Nm and the total power 1700 W. To prevent needing a gearbox, the maximum rpm of the actuator should be equal to:

Hence, [math]\displaystyle{ \omega }[/math] is equal to 4000 rpm. The required power can be distributed over four actuators. Therefore, each actuator needs a power of 425 W, a torque of 6.25 Nm and a maximum of 4000 rpm. The Transmotec D123182-12 fits the power requirements running at a slightly lower rpm. This actuator weighs approximately 7.5 kg. In total the actuators have a weight of 30 kg.

Finally, the actuators, screen and computer components have to be supplied with power. The actuators need to provide a mechanical power of 1700 W. The efficiency of an electric motor is dependent of the work load of the motor. If the efficiency is assumed 70%, the required electric power is equal to 2500 W. On top of that, the screen has an electric power of 130 W. Finally, the processing power of the computer is approximated at 1000 W. The sensors also require power combined with the additional lighting, this amounts to a total electric power of 4 kW. Assuming that the batteries can charge at the end of the day, the robot needs to be functional for eight hours. Therefore, the batteries need to store 32 kWh, if losses are neglected. The capacity of a lithium-ion battery is 265 Wh/kg . This means the battery pack would weigh 120 kg. This is not feasible, therefore, it is assumed that the robot can charge during the day. If the robot has an operating duration of two hours, the battery needs a capacity of 8000 kWh. This would result in a mass of 30 kg.

In total, the robot would weigh approximately 120 kg. Next to mass, volume is an important factor. The battery has an energy density of 693 Wh/L. Therefore, the battery pack has a volume of 12 L. The actuators have a combined volume of 9 L.

Appearance

If the previous approximations are taken into account, the parking assistant robot could take the following appearance:

A possible appearance for the parking assistant robotic system.

The interior of the parking assistant robotic system.

In the figure above, the interior of the robot can be observed. Each of the wheels is driven with a motor. Although the road in a parking garage is often smooth, the robot should also be able to cross speed bumps. For this reason, the motor and wheels are attached to the chassis with a double wishbone suspension. The spring-damper combination needs to be critically damped for the best performance. Hence, the spring stiffness and damping coefficient have to be determined. This can be done with the use of the following formulas:

With ω_n the natural frequency in rad/s, k the spring stiffness in N/m and m the mass in kg.

With ζ the damping ratio and c the damping coefficient in N s/m

With ω_d the damped frequency in rad/s .

The unsprung mass is equal to 50 kg. Hence, the sprung mass is equal to 70 kg.

Conclusion

Discussion

Planning

	Activities	Person(s)
Week 1	Introduction lecture Brainstorm on possible subjects Choosing subject Literature study	All All All All
Week 2	Tutor meeting 1 Problem definition State of the Art research User analysis Possible solutions Planning Updating wiki page	All Sietse Luc Mandy Tar Rien All
Week 3	Tutor meeting 2 Improvement RPC's Research user interaction possibilities Concepting on hardware solutions Start on parking tracking software Updating wiki page	All Mandy + Luc Rien Sietse Tar All
Week 4	Tutor meeting 3 Reforming wiki page to make it more cohesive Research in hardware concepts necessities Continuing parking tracking software User interaction analysis and making survey Updating wiki page	All Luc Sietse Tar Mandy + Rien All
Week 5	Tutor meeting 4 First design hardware solution Distributing survey for user interaction methods Writing part about user interaction Translate user feedback in improvement points for design Continuing on software Updating wiki page	All Sietse Name All Name Name All
Week 6	Tutor Meeting 5 Finishing hardware solution design, with user feedback Finishing software Finishing user, society and enterprise part in wiki Brainstorm and first start on the visuals Updating wiki page	All Name Name Name Name All
Week 7	Tutor meeting 6 Start on presentation Finishing wiki page Writing conclusion Writing discussion Working on the visuals	All Name Name Name Name Name
Week 8	Tutor meeting 7 Finishing presentation Final presentation Finishing visuals Finalizing project	All Name Name Name Name

Log

Week 1

Name	Hours	Summary
Luc	15	Introduction lecture, two meetings, brainstorm on possible subjects, literature study, written: State-of-art
Mandy	15	Introduction lecture, two meetings, brainstorm on possible subjects, literature study, written: User, Society, and Enterprise
Rien	15	Introduction lecture, two meetings, brainstorm on possible subjects, literature study
Sietse	17	Introduction lecture, two meetings, brainstorm on possible subjects, literature study, problem statement, RPCs
Tar	10	Introduction lecture, two meetings, brainstorm on possible subjects, literature study

Week 2

Name	Hours	Summary
Luc	10	Two meetings, RPC's
Mandy	10	Meeting with tutor, meeting with group afterwards, improved: user, society, enterprise, researched valet parking costs
Rien	10	Two meetings, RPC's
Sietse	9	Concepting: researching and drawing partial solutions, and drawing entire solutions.
Tar	6	Two meetings, Concept descriptions

Week 3

Name	Hours	Summary
Luc	5	Meeting Tutor + Meeting Group afterwards, Meeting RPC's with Mandy: improved RPC's
Mandy	5	Meeting Tutor + Meeting Group afterwards, Meeting RPC's with Luc: improved RPC's
Rien	5	Meeting Tutor + Meeting Group afterwards, concepting hardware solutions
Sietse	5	Meeting Tutor + Meeting Group afterwards, devising and drawing a new four wheel omnidirectional concept
Tar	18	Meeting Tutor + Meeting Group afterwards, wrote something about objectives and other small sections, started parking tracking software

Week 4

Name	Hours	Summary
Luc	10	Meeting Tutor + 2x Meeting group, changing wiki and making it more coherent, working on the survey for the user-robot interaction
Mandy	11	Meeting tutor + 2x Meeting Group, Meeting with Rien about the communication of the robot and the survey, Meeting with Luc and Rien to finish the survey
Rien	X	Summary
Sietse	20	Meeting Tutor + 2 x Meeting group, researching and approximating important robot parameters (required motors, wheel, battery pack, etc.), creating 3D geometry of body, Rendering geometry.
Tar	18	Meeting Tutor + 2 x Meeting group, improved parking search algorithm, wrote some text about software, started parking lot editor

Week 5

Name	Hours	Summary
Luc	8	Meeting with tutor, finished the survey and spread the survey, worked on the wiki page, meeting to process the data obtained by the survey
Mandy	6	Meeting with tutor, finished the survey and spread the survey, meeting to process the data obtained by the survey
Rien	X	Summary
Sietse	8	Meeting with tutor, creating 3D parking space environment for presentation video, writing the primary user chapter
Tar	13	Meeting with tutor, finished parking lot editor, created a simple parking lot, improved search algorithm and added spot management

Week 6

Name	Hours	Summary
Luc	10	Meeting with tutor, Meeting with Jordy Senden about our project, Meeting with group, 2 Meetings to work on the data of the survey
Mandy	10	Meeting with tutor, Meeting with Jordy Senden about our project, Meeting with group, 2 Meetings to work on the data of the survey
Rien	X	Summary
Sietse	X	Summary
Tar	X	Summary

Week 7

Name	Hours	Summary
Luc	X	Summary
Mandy	X	Summary
Rien	X	Summary
Sietse	X	Summary
Tar	X	Summary

Week 8

Name	Hours	Summary
Luc	X	Summary
Mandy	X	Summary
Rien	X	Summary
Sietse	X	Summary
Tar	X	Summary

References