FOR A CAR OR THE LIKE

The present invention relates to a method for finding a free parking space for a car or the like performed on a computing entity or the like.

The present invention further relates to a system for finding a free parking space for a car or the like, preferably for performing with a method according to one of the claims 1 -14.

To find a free parking space in a city is often a tedious task for a driver accompanied by wasting time, energy and pollution caused by the drivers searching for a free parking space. In order to reduce the time, energy, etc. numerous methods and systems have been described to guide users to the "best" free parking space. For example in US 7 834 778 or in US 5 910 782 systems are shown that are based on directories of parking lots, in particular with online- reservation systems for parking spaces. Further in US 6 147 624 technical systems are used to sense an occupation of parking space. In the non-patent literature of Gregor Josse, Matthias Schubert, and Hans-Peter Kriegel. 2013, "Probabilistic parking queries using aging functions", in Proceedings of the 21 st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL'13), ACM, New York, NY, USA, 452-455, DOI=10.1 145/2525314.2525458 http://doi.acm.org/10.1 145/2525314. 2525458 a method for finding a free parking space is disclosed taking the probability into account that a parking space becomes occupied again.

In the non-patent literature of Xu, Bo, et al, "Real-time street parking availability estimation", Mobile Data Management (MDM), 2013 IEEE 14th International Conference on. Vol. 1. IEEE, 2013 a system is disclosed to estimate from experience the availability of parking space in a city block.

All these afore-mentioned conventional systems are based on the principle to select a suitable parking space and then guide the driver towards it. One of the disadvantages is however that they do not capture the situation in many city districts, especially in Europe, where the main source of parking space is located along the road side and neither an occupation sensing nor a reservation technology/system is available. Therefore, the drivers intuitively try to find a parking space in the following way: A driver drives to the destination and then searches for a parking space by circling around the destination looking for a free parking space along the road to park the car. This becomes in particular bothersome when the destination is in a neighbourhood not well known to the driver so that the driver cannot rely on his/her experience on where the likelihood to find a suitable parking space is high.

It is therefore an objective of the present invention to provide a method and a system for finding a free parking space for a car or the like which enable to find a free parking space with a higher reliability then conventional methods and systems while being fast and efficient.

It is a further objective of the present invention to provide a method and a system for finding a free parking space for a car or the like being easy to implement and which do not require extensive additional devices.

It is an even further objective of the present invention to provide a method and a system for finding a free parking space for a car or the like being more flexible in terms of an extension or an enhancement.

It is an even further objective of the present invention to provide a method and a system for finding a free parking space for a car or the like which do not require stationary sensing devices and which take into account parking spaces along a road or street.

The aforementioned objectives are accomplished by a method of claim 1 and a system of claim 15. In claim 1 a method for finding a free parking space for a car or the like performed on a computing entity or the like is defined. According to claim 1 the method is characterized by the steps of

a) Setting a trade-off between at least the following two parameters by setting means or entity:

time for searching a free parking space - search time - and

- distance of the parking space to a selected destination,

b) Calculating an optimal route by calculating means or entity to a free parking space based on a probabilistic parking space model - PPSM - and based on the set trade-offs according to step a) using a street network. In claim 15 a system for finding a free parking space for a car or the like, preferably for performing with a method according to one of the claims 1 -14 is defined.

According to claim 15 the system is characterized by

a destination selection entity adapted to select a destination,

a setting entity adapted to set a trade-off between at least the following two parameters:

time for searching a free parking space - search time - and

- distance of the parking space to the selected destination,

a calculation entity adapted to calculate an optimal route to a free parking space based on a probabilistic parking space model - PPSM - and based on the set trade-off using a street network. The term "entity" refers to a device or a plurality devices connected to each other for operating together and being adapted to perform one or more tasks in particular computing tasks. An entity may be a personal computer, a tablet a smartphone, a car navigation device, a processor or the like. The term "probabilistic parking space model" refers in particular to a model representing the probability for a free parking space at a certain time and in a certain distance to a certain location. According to the invention it has been recognized that in particular due to the probabilistic model PPSM the present invention does not depend or rely on the installation of parking sensors or other technologies and is therefore much more widely applicable than conventional methods and systems. For example the present invention can be applied in the area of autonomous driving such that a driver only selects its destination and the car autonomously drives the car to the destination and find a free parking space within the vicinity of the destination.

According to the invention it has been further recognized that due to the probabilistic parking space model PPSM the time, the energy and pollution caused by drivers searching for free parking space is significantly reduced.

According to the invention it has been even further recognized that no permanent internet connection is required and can in principle work completely offline saving costs and communication resources.

According to the present invention it has been even further recognized that the implementation barrier is very low as it only requires a conventional car navigation system using a GPS receiver, some storage and some additional meta-data about streets or roads and some processing capabilities.

Further features, advantages and preferred embodiments are described in the following subclaims.

According to a preferred embodiment at least one of the following parameters: User related parameters representing price of parking space, expected time, safety or the like and representing the number of times passing the same street segment of a calculated optimal route is set and included in the calculation according to step b). This enables in an easy way to refine the calculation of the optimal route leading to an increased flexibility: users can more accurately express their preferences. Further the effectiveness as perceived by the driver/user is increased.

According to a further preferred embodiment said trade-off is set by visualizing one or more sliders to a user for said parameters, setting said sliders by the user and determining the trade-off based on the set sliders. This enables a driver to easily set the trade-off between at least two of the parameters mentioned above. In case of more than two parameters a user or driver may for example set a slider for each parameter between a value of 0 and 1 and based on these set sliders the trade- offs or relative weights of these parameters are determined.

According to a further preferred embodiment the optimal route is input to a driver's guiding system and used for guiding a driver along the optimal route. Therefore, the driver simply selects the destination and activates for example the option in his car navigation system to find a free parking space. Further user interaction is not required anymore providing a fast and efficient way to find a free parking space.

According to a further preferred embodiment said PPSM is based on a probability that a free parking space is on a certain segment of a street and a dynamicity of said street segments' parking spaces, preferably wherein said probability is time- dependent. This enables to provide pieces of information about each street segment to calculate an optimal route later: the probability that there is a free parking space on the street segment and the dynamicity of the street segment parking spaces, i.e. information about how quickly occupied parking spaces become free again. The probability that there is a free parking space on the street segment can simply be expressed by a real number between 0 and 1.

According to a further preferred embodiment said probability is made aware to a user, preferably visualized by a bar, wherein said bar may have different colors, and/or made audible by a sound. For instance when said probability is visualized to a user by a bar, said bar additionally may have different colors, e.g. green for a probability greater than 75%, yellow for a probability between 50% and 75% and so on. Further sounds can additionally or alternatively be associated to a probability when indicating it to a driver. According to a further preferred embodiment said dynamicity is provided in form of a time value representing the time how long it takes until the probability of free parking space reaches again a normal or average value over time. This enables to represent in an easy while precise way the dynamicity. Preferably after observing that there is no free parking space on some street segment its parking space probability may be set to 0. As time passes while searching other street segments by a driver the probability for a free parking space on the street segment gradually increases until it has reached its normal value.

According to a further preferred embodiment said trade-off is expressed as a weighted sum having a weight for each parameter. For example the user may select a weight w between 0 and 1 for the search time and the probabilistic parking space model then computes a route that minimizes the expected value of w T + (1 -w) D where T is the time required for searching and D is the walking distance to the destination.

According to a further preferred embodiment step b) is performed by using heuristics, preferably local search and/or genetic procedures. The optimization problem for calculating an optimal route can then be solved near-optimal with conventional methods and provides a reliable near-optimal route with sufficient precision/reliability as optimal route for the driver.

According to a further preferred embodiment said street network is implemented as a directed graph. For example, the directed graph has a function of the set of street crossings and a function of the set of street segments between these crossings. This enables an easy implementation and fast processing when calculating an optimal route. According to a further preferred embodiment in step b) first plurality of routes is calculated and second the one having the best trade-off is selected as optimal route. This enables an efficient selection by considering a plurality of possible routes. If multiple routes have the same "best" trade-off the driver may select one of these routes or e.g. the driver is asked to provide further parameters or one of these routes is selected randomly.

According to a further preferred embodiment when a free parking space is found and/or when a parking space to which an optimal route was calculated is occupied this information is used for updating the probability and/or dynamicity of parking spaces of the PPSM. This enables allows in an easy way to further refine the probabilities for finding a free parking space when, for example, a driver founds a free parking space along the route to the calculated free parking space or the calculated free parking space is occupied. Preferably step b) is performed again when no free parking space has been found taking into account probabilities of determined occupied or free parking spaces along the route.

According to a further preferred embodiment said information is collected from different users, preferably aggregated, and redistributed to the users for updating the PPSM. This further enables a more precise optimal route to a free parking space, since the probabilities are taking into account from a plurality of users having a broader basis for calculating the optimal route as well as a more actual "picture" of occupied and non-occupied parking spaces within the vicinity of the destination. Further, when the information is aggregated, this information can be evaluated, for example by a parking space provider or a management of a city to provide new parking spaces within certain areas.

According to a further preferred embodiment when real-time occupation data of parking spaces is available, this information is additionally used in step b). This enables to enhance the PPSM even more: For example in some areas parking spaces may be equipped with sensors indicating occupancy or non-occupancy of a parking space. Then this information can additionally be used when calculating an optimal route to a free parking space. Thus user satisfaction is even more increased and the probability of finding a free parking space is increased.

There are several ways how to design and further develop the teaching of the present invention in an advantageous way. To this end it is to be referred to the patent claims subordinate to patent claim 1 on the one hand and to the following explanation of preferred embodiments of the invention by way of example, illustrated by the figure on the other hand. In connection with the explanation of the preferred embodiments of the invention by the aid of the figure, generally preferred embodiments and further developments of the teaching will be explained.

In the drawings

Fig. 1 shows a system according to a first embodiment of the present invention; and

Fig. 2 shows steps of a method according to a second embodiment of the present invention.

Fig. 1 shows a system according to a first embodiment of the present invention.

In Fig. 1 a system 1 is shown comprising a probabilistic parking space model entity providing the PPSM 3, a guiding system 10 and a positioning system 1 1. When a driver D selects a destination 2a and its parking preferences 2b this information 2a, 2b is input into the system 1 and used as input for the probabilistic parking space model 3 to calculate an optimal route to the destination. The outcome of the calculation according to the probabilistic parking space model 3 is an optimal route/search route 4, comprising route information to a free parking space. This search route 4 is then input into a guiding system 10. Further a positioning system 1 1 uses the actual position of the car of the driver D and inputs position information 5 into the guiding system 10. The guiding system 10 then uses the input position information 5 and the search route 4 to give driving directions 6 to the driver D.

In other words the driver D selects the destination 2a and parking preferences 2b, wherein the parking preferences is a trade-off at least between the time needed to find a parking space and the distance to the destination 2a. The parking preference may be selected by a graphical slider by a driver D. The probabilistic parking space model PPSM entity 3 calculates a route that optimizes the expected time needed to find a parking space and the expected distance to the destination based on the set trade-off 2b between those two criteria selected by the driver D. The calculated search route/optimal route 4 is then passed to the guiding system 10. The latter guides the driver D along the search route 4. In the following the probabilistic parking space model PPSM is described in more detail:

The Probabilistic Parking Space model PPSM uses at least two pieces of information about each street segment: (a) the probability that there is a free parking space on the street segment and (b) the dynamicity of the street segment's parking spaces, i.e. information about how quickly occupied parking spaces become free again.

The probability (a) can simply be expressed by a real number p between 0 and 1. As for (b), a possible representation model is to consider a time value t expressing how long it is expected to take until the probability for a free parking space converges back to its normal value p. More specifically, after observing that there is no free parking space on some street segment S, its parking space probability is set to 0. As time passes while searching other street segments, the probability for a free parking space on S gradually increases until it has reached p again.

The trade-off between search time and distance to the destination 2a can be expressed as a weighted sum. The user or driver D selects a weight w between 0 and 1 for the search time, the Probabilistic Parking Space model PPSM computes a route that minimizes the expected value of w + (1 -w) D, where T is the time required for searching and D is the walking distance to the destination.

As computing the best trade-off is a complex optimization problem, a preferred embodiment is not to solve it optimally, but use heuristics like local search or genetic algorithms and use the result as optimal route.

The PPSM can be mathematically formalized as follows: A street or road network is represented as a directed graph G=(V,E), where V represents the set of street crossings and E is the set of street segments between these crossings. For each edge e in E he time required to travel along e, say t(e) is provided, the probability that there is a free parking space on e, say p(e), and the time u(e) it takes until the probability of a free parking space has converged back to p(e) after having observed that road/street segment e has no free parking space. In particular, if the last time the segment e has been observed not to have a parking space at time t' and the current time is t, then the probability to have a free parking space now calculates as min{ p(e), (t-f) / u(e) ^■ p(e) }.

Given an initial location A and a destination B, and given the value of the weight w, the probabilistic parking space model PPSM is used to define the optimal search route for a parking space. In this context, a search route is a sequence of edges ei,...e _n from the edge set E such that ei has the initial location A as the starting point and the end point of each edge e, in the sequence is the starting point of the subsequent edge ei+i. The same edge from E can appear more than once in a search route.

Given a search route ei ...e _n , the probability p, that a parking space is found while searching on the i-th edge of the search route can be calculated as follows: let j(i) denote the largest index smaller than i with ej = e, , or j(i) = undefined if there is no such index. Then p, is recursively calculated as

Pi = P(no parking space found before e,) ^■ P(parking space is found at e,)

= (1 -pi-i ) ^■ min {p(e,), ( t(e _j( i)+ ) + ί(βχί ₎₊₂ ) + ... + t(en) ) / u(e,) ^■ p(e,) } In case j(i) is undefined, the second factor of the above formula is replaced simply by p(ei).

From these probabilities, the expected distance to the destination is calculated as D = pi dist(ei.B) + ... + p _n dist(e _n ,B) , and the expected travel time is calculated as

T = pi 0.5 t(ei) + P2 (t(ei) + 0.5 t(e ₂ ))

+ p ₃ (t(ei) + t(e ₂ ) + 0.5 t(e ₃ ))

+ ...

+ p _n (t(ei) + .. + t(e _n -i) + 0.5 t(e _n ))

It is assumed here that whenever a parking space is found on a road or street segment, it is found after an expected time that is half of the time needed to traverse the road segment. In order for the above calculations to be correct, the overall probability that a parking space is found is required be 1. This is achieved only if either one of the road segments has probability 1 to have a free parking space, or if the search route is infinite. For the above formulae to give a good indication of the expected search time and parking distance in practice, it preferably suffices that the probability to find a parking space is close to one.

In the following a procedure is given to compute an approximation of the optimal search route. Said procedure is based on the idea to find the best search path that uses some fixed number of n street segments. As the number of solutions the procedure considers is exponential in n, this fixed number is preferably chosen small enough so that the computation terminates within reasonable amount of time. Candidate solutions are evaluated by the procedure using a slight variation of the above formula. This variation is needed to compensate for the fact that due to the small n the probability to find a parking space when driving through these n road/street segments might be significantly smaller than 1. For this reason, the procedure assumes certain expected values D _n +i and T _n +i for the travel time and the distance that are going to apply if no parking space is found among the n edges of the candidate solution. The formulae for D and T therefore change to

D = pi dist(ei.B) + ... + p _n dist(e _n ,B) + (1 - pi - .. - p _n ) D _n+ i

T = pi 0.5 t(ei) + P2 (t(ei) + 0.5 t(e ₂ ))

+ p ₃ (t(ei) + t(e ₂ ) + 0.5 t(e ₃ ))

+ ...

+ p _n (t(ei) + .. + t(e _n -i) + 0.5 t(e _n ))

+ (1 - pi - .. - Pn) Tn+1

A useful value for D _n +i is preferably the average distance of the edges ei ...e _n to the destination, and a useful value for T _n +i is preferably a constant. This constant represents the average time needed to find a parking space in the searched area. The larger this constant is chosen, the more attractive it becomes to search on road/street segments having a high probability for a free parking space.

The procedure enumerates all search paths and selects the one with the best tradeoff between search time T and distance D to the destination, using the user- provided weight w to balance between these two criteria. If the user or driver does not find a parking space on the n road segments, the procedure computes n new road segments using the same mechanism again, but this time taking into account probabilities that might be decreased because street segments have been unsuccessfully visited before. This process is repeated until a parking space is found.

Alternatively, the procedure can re-compute the best search route every time the driver has visited only the first road segment ei of the current search route. Preferably the search route is adapted in real-time. If the driver D does not follow the suggested search route 4 while looking for a free parking space, for example because of blocked roads or personal preferences, the probabilistic parking space model PPSM may compute updated search routes based on the knowledge that there was no free parking space along road segments that the driver already visited. A recomputation may also be performed when the travel time for a road/street segment significantly deviates from what the PPSM model has predicted. The present invention can be easily integrated into regular car- and navigation- systems. A regular car navigation system may switch in the parking space searching mode as soon as the driver D is close enough to the destination. Additionally the navigation system can be used to recognize when a user has found a free parking space. This information may be used to update the PPSM with new probabilities. Information updates from several drivers or users can be aggregated in order to make the experience of single users/drivers available to all other users/drivers. Preferably the data before aggregating is anonymized, so that security of the users is not affected. Statistical data on parking space availability based on the aggregated additional data can also be provided by owners of shopping centers or by city authorities or the like.

Further, the PPSM may be preferably combined with real-time parking information systems. When real-time sensor information on the occupation of parking spaces is available it can be taken into account by the PPSM. In this case the probability of parking space at a respective road segment is set to 1 whenever sensor information indicates that a parking space is free. Of course, additional criteria for parking spaces like prize, maximum parking time, safety or the like can be taken into account by the PPSM. Further the number of times the same street or road segment is passed can be used as criteria to minimize in order to increase the effectiveness as perceived by the driver/user. Additionally the PPSM may be time dependent implemented. As the availability of parking spaces is different at different day times and different weekends, the PPSM can use different probabilities for different times. For example, in a residential area it is less likely during night time that a currently free occupied street or road segment will have a free parking space, soon. On the other hand to find free parking space in a shopping area will be higher then during time.

Fig. 2 shows steps of a method according to a second embodiment of the present invention. In Fig. 2 steps of a method for finding a free parking space for a car or the like are shown.

In a first step S1 a trade-off is set between at least the following two parameters by a setting means or one or entities: Time for searching a free parking space - search time - and distance of the parking space to the selected destination.

In a second step S2 a optimal route is calculated by calculating means or entities to the free parking space based on a probabilistic parking space model - PPSM - and based on the set trade-off according to step S1 using a street network.

The present invention has inter alia the following advantage: The present invention is much more widely applicable than conventional technologies since, in particular it does not depend on the installation of parking sensors or other costly technologies.

To summarize the present invention enables a computation of an optimal route with possibly including loops for searching for a free parking space based on a user's preference between search time and distance to the destination which is totally in contrast to all conventional systems which are based on the approach to select the most suitable parking space and then navigate towards it.

The present invention further enables to use a probabilistic model for parking space availability on road segments taking into account the dynamics of parking spaces becoming free.

In particular the present invention preferably provides a method for finding a free parking space comprising the steps of: receiving from a user a preferred trade-off between search time and distance to the destination, calculate an optimal or near- optimal route to search for free parking space based on a probabilistic model on the availability of parking spaces on road segments and passing a computed search route to the navigation system of a car of a driver, so that the navigation system can guide the driver along the search route to a free parking space. Many modifications and other embodiments of the invention set forth herein will come to mind to the one skilled in the art to which the invention pertains having the benefit of the teachings presented in the foregoing description and the associated drawings. Therefore, it is to be understood that the invention is not to be limited to the specific embodiments disclosed and that modifications and other embodiments are intended to be included within the scope of the appended claims. Although specific terms are employed herein, they are used in a generic and descriptive sense only and not for purposes of limitation.