Device and method for outputting navigation information, and vehicle

Abstract

A device and a method for outputting navigation information for a vehicle are provided. Position data, destination data, and parking data containing information relating to at least two parking space positions and the availability of parking spaces at the at least two parking space positions can be provided via an input interface. A data processing device is configured to determine an order in which at least some of the at least two parking space positions should be approached based on the provided position data, destination data and parking data in such a manner that the determined order meets an optimization criterion. The data processing device is also configured to check whether the optimization criterion can be met by waiting at the at least one parking space position or by returning to a parking space position to be approached before the at least one parking space position.

Claims

1. An apparatus that outputs navigation information for a vehicle, the apparatus comprising: at least one input interface, via which position data is provided including information with respect to a present position of the vehicle, destination data including information with respect to a destination position of a destination being traveled toward by the vehicle, and parking data including information with respect to at least two parking space positions and an availability of parking spaces at the at least two parking space positions; a data processor programmed to determine a sequence in which at least a part of the at least two parking space positions is to be approached based on the position data, the destination data, and the parking data such that the sequence meets an optimization criterion, and at a same time to check for at least one of the parking space positions whether the optimization criterion can be met by waiting at the at least one parking space position or returning to a parking space position to be approached chronologically before the at least one parking space position; and at least one output interface, via which the sequence can be output as navigation information; wherein the data processor is programmed to determine whether the optimization criterion can be met by waiting at the at least one parking space position in consideration of costs which result from a first availability model, which depicts a chronological development of the availability of parking spaces at the at least one parking space position.

2. The apparatus according to claim 1, wherein the first availability model, which is based on an exponential distribution, relates an availability rate, according to which parking spaces are available at the parking space position to a waiting time at the at least one parking space position.

3. The apparatus according to claim 1, wherein the data processor is designed to influence the costs resulting from the first availability model by specifying a probability, with which a parking space will become available by waiting at the at least one parking space position.

4. The apparatus according to claim 1, wherein the data processor is designed to determine whether the optimization criterion can be met by returning to a parking space position to be approached chronologically before the at least one parking space position in consideration of a conditional availability of parking spaces at the parking space position to be approached chronologically before the at least one parking space position, which results from a second availability model, which depicts the chronological development of the availability of parking spaces at the parking space positions to be approached chronologically before the at least one parking space position.

5. An apparatus that outputs navigation information for a vehicle, the apparatus comprising: at least one input interface, via which position data is provided including information with respect to a present position of the vehicle, destination data including information with respect to a destination position of a destination being traveled toward by the vehicle, and parking data including information with respect to at least two parking space positions and an availability of parking spaces at the at least two parking space positions; a data processor programmed to determine a sequence in which at least a part of the at least two parking space positions is to be approached based on the position data, the destination data, and the parking data such that the sequence meets an optimization criterion, and at a same time to check for at least one of the parking space positions whether the optimization criterion can be met by waiting at the at least one parking space position or returning to a parking space position to be approached chronologically before the at least one parking space position; and at least one output interface, via which the sequence can be output as navigation information; wherein the data processor is designed to determine whether the optimization criterion can be met by returning to a parking space position to be approached chronologically before the at least one parking space position in consideration of a conditional availability of parking spaces at the parking space position to be approached chronologically before the at least one parking space position, which results from a second availability model, which depicts the chronological development of the availability of parking spaces at the parking space positions to be approached chronologically before the at least one parking space position; and wherein the second availability model, which is based on a Markov chain, relates a parking rate, according to which parking spaces are occupied at a parking space position, to an availability rate, according to which parking spaces become available at the parking space position.

6. A motor vehicle comprising the apparatus according to claim 1.

7. A method for navigation of a vehicle, the method comprising: providing position data including information with respect to a present position of the vehicle; providing destination data including information with respect to a destination position of a destination being traveled toward by the vehicle; providing parking data including information with respect to at least two parking space positions and an availability of parking spaces at the at least two parking space positions; determining a sequence, in which at least a part of the at least two parking space positions is to be approached based on the position data, the destination data, and the parking data such that the sequence meets an optimization criterion, and at a same time is checked for at least one of the parking space positions whether the optimization criterion is met by waiting at the at least one parking space position or returning to a parking space position to be approached chronologically before the at least one parking space position; and outputting the sequence as navigation information; wherein whether the optimization criterion can be met by waiting at the at least one parking space position is determined in consideration of costs which result from a first availability model, which depicts a chronological development of the availability of parking spaces at the at least one parking space position.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 shows an example of a device for outputting navigation information;

(2) FIG. 2 shows an example of an ascertained sequence in which parking space positions are to be approached; and

(3) FIG. 3 shows an example of the ascertainment of a sequence in which parking space positions are to be approached.

DETAILED DESCRIPTION OF THE DRAWINGS

(4) FIG. 1 shows an example of a device 1 for outputting navigation information N for a vehicle having three input interfaces 2a, 2b, 2c, a data processing unit 3, and an output interface 4.

(5) Position data L, which contain information with respect to the present position of the vehicle, can be provided via a first input interface 2a. The first input interface 2a can establish a data connection to multiple satellites for this purpose, for example, in order to ascertain the present position of the vehicle on the basis of signals received via this data connection.

(6) Destination data Z, which contain information with respect to the position of the destination being traveled toward by the vehicle, can be provided via a second input interface 2b. The second input interface 2b can acquire an input of the driver of the vehicle for this purpose, for example, by means of a keyboard, a touchscreen, or a microphone, for example, from which the destination, in particular an address, emerges.

(7) Parking data P, which contain information with respect to at least two parking space positions and the availability of parking spaces at the at least two parking space positions, can be provided via a third input interface 2c. The third input interface 2c can for example have an air interface for this purpose and can be designed, to establish a data connection to a parking information service, for example via a wireless Internet connection, wherein the parking data P can preferably be retrieved from a server. Alternatively or additionally, the third input interface 2c can have a database or can be connectable to a database, which contains the parking data P.

(8) The data processing unit 3 is designed to ascertain, on the basis of the position data L, the destination data Z, and the parking data P, a sequence in which at least two parking space positions are to be approached by the vehicle on the search for a parking space in the region of the destination being traveled toward, preferably to find a parking space at one of these parking space positions with a probability predetermined, for example, at the factory or by the driver, for example via the second input interface 2b. The sequence is ascertained here in such a way that an optimization criterion is met, for example the total travel time is minimal, which depicts the required time for the travel from the present position of the vehicle until finding a parking space and a walk from the parking space position at which a parking space was found to the destination being traveled toward.

(9) The data processing unit 3 is preferably designed here to apply various procedures for the parking space search, in particular to combine them with one another. A first procedure is, for example, approaching multiple parking space positions in succession, preferably in dependence on a travel route to be covered between the parking space positions, the respective distance between each of the parking space positions and the destination being traveled toward and/or among one another and/or the availability of parking spaces at the parking space positions, i.e., the probability of finding a free parking space upon approaching the parking space positions.

(10) A second procedure is, for example, waiting at a parking space position to be approached until a parking space becomes free at this parking space position P.sub.i. A third procedure is, for example, approaching one or more parking space positions multiple times, i.e., returning to a parking space position already previously approached. In the second and third procedure, a future occupancy of the parking spaces at the parking space positions P.sub.i is preferably taken into consideration. The future parking space occupancy, in particular the chronological development of the parking space occupancy, can be modeled, for example, by means of an availability model, in particular in consideration of an availability rate, at which parking spaces become free at the corresponding parking space position P.sub.i. The availability rate can be or can have been empirically ascertained or estimated, for example.

(11) To find the sequence optimized with respect to the total travel time of the driver, the data processing unit 3 can apply, for example the so-called branch-and-bound method. A strategy tree is preferably developed in this case, the branches of which depict the various possible sequences. The development of a branch can be terminated, i.e. the corresponding sequence can be discarded, if the optimization criterion cannot be met in this branch, i.e., for example, if a parking space can be found with the same probability in another branch of the strategy tree in a shorter time and/or at a shorter distance from the destination being traveled toward. Alternatively or additionally, the development of a branch can be terminated if the minimum expected travel time cannot be achieved.

(12) In the ascertainment of the optimum sequence, the data processing unit 3 preferably takes into consideration costs which result due to the trips between the various parking space positions and/or due to waiting at a parking space position. The costs preferably depict the required time which is linked to carrying out a strategy, and can be ascertained by corresponding cost functions.

(13) The sequence thus ascertained can be output via the output interface 4, for example via a display unit and/or a loudspeaker as navigation information N.

(14) FIG. 2 shows an example of an ascertained sequence in which parking space positions P.sub.i with i=1 . . . 6 are to be approached. The parking space positions P.sub.i are shown together with a present position P.sub.0 of a vehicle and a position F of a destination being traveled toward on a map. Each parking space position P.sub.i is assigned an availability p.sub.πi with i=1 . . . 6 of parking spaces, shown as a pie chart, which corresponds to a probability of finding a free parking space at the corresponding parking space position P.sub.i upon the, in particular initial approach.

(15) In the example shown, it is assumed that the driver of the vehicle wants to go from the position P.sub.0 to the destination F being traveled toward. The driver obviously first requires a parking space and then has to cover the last section on foot. At each of the parking space positions P.sub.i, he has the option of waiting until a parking space becomes available or testing out another parking space position P.sub.i. The approach can be repeated until the driver finally finds a parking space or waits for free parking space at a parking space position P.sub.i.

(16) Solely by way of example, a route R is shown as a solid wide line, which corresponds to a strategy optimum for the driver, i.e., traveling along the parking space positions P.sub.i in an optimum sequence to reach the destination F with minimal costs, in particular in the shortest time. In this case, preferably only routes R or sequences are accepted which have a success rate of 90% or higher.

(17) Parking attempts P′ are indicated by empty circles. In the present case, not all parking space positions P.sub.i are approached. The driver first attempts to find a parking space at parking space position P.sub.4, and drives further to parking space position P.sub.2 if he is not successful. He then drives on at parking space position P.sub.3 to look for a parking space, if he is again not successful. Upon reaching the parking space position P.sub.3, the probability, which is cumulative in particular, of having found a parking space is greater than 90%. If the driver still should not have found a parking space up to parking space position P.sub.3, he can wait at parking space position P.sub.3 until a parking space becomes free there. The pedestrian route to be covered in the case of success is shown as a dashed black line.

(18) FIG. 3 shows an example of the ascertainment of a sequence in which parking space positions P.sub.i with i=1 . . . n are to be approached using a vehicle. The possible parking space positions P.sub.i are indicated by numbered circles arranged horizontally adjacent to one another. From each of the parking space positions P.sub.i, either another parking space position P.sub.i can be approached, or it is possible to wait at the corresponding parking space position P.sub.i until a parking space becomes free. These options are indicated by arrows, so that starting from a present position P.sub.0 of the vehicle, a strategy tree results, the branches of which each form a sequence of parking space positions P.sub.i to be approached. One of these sequences is indicated by the black dashed line. According to this sequence, the vehicle is firstly to approach the position P.sub.i. If a free parking space is not available there, the parking space position P.sub.i-1 is thus to be approached. If a free parking space is not available there right away, the driver should wait there until a parking space becomes free.

(19) Each possible sequence represents a strategy π for finding a parking space, which is successful with a cumulative probability at which a parking space is to be found in the parking space positions P.sub.i contained in the sequence. The probability of being successful after approaching j various parking space positions P.sub.i is with as the availability of a parking space at the parking space position P.sub.i. The success
p.sub.π.sup.j=(1−p.sub.π.sub.i) . . . (1−p.sub.π.sub.j-1)p.sub.πj
with p.sub.π.sub.i as the availability of a parking space at the parking space position P.sub.i. The success rate of a specific strategy π with m attempts of finding a parking space at various parking space positions P.sub.i therefore results as

(20) $p_{\pi }=\underset{j=1}{\overset{m}{.Math.}}{p}_{\pi }^j.$

(21) Since the success rate increases with each additional attempt to find a parking space at a further parking space position P.sub.i, the strategy tree is finite, wherein each branch of the strategy tree ends when the success rate p.sub.π corresponding to it is greater than a predetermined probability p.sub.acc of finding a parking space.

(22) The optimum sequence is ascertained in consideration of costs which result due to following the different strategies and preferably correspond to the required total time until a parking space is found and from there the destination being traveled toward is reached on foot. To ascertain costs which result due to driving with the vehicle or a walk, for example, from the present position P.sub.0 of the vehicle to a parking space position P.sub.i or from a parking space position P.sub.i to a parking space position P.sub.i or from a parking space position P.sub.i to the destination being traveled toward, route calculation methods are known from the prior art, such as Nokia HERE, Grasshopper, or Google routing.

(23) Cost functions can be assumed here, which quantify the costs of the above-mentioned driving or walking times, possibly also in dependence on a state of the vehicle, for example an orientation of the vehicle on the road.

(24) To calculate the costs of a strategy π, according to which the vehicle should wait at a parking space position P.sub.i, a first availability model can be taken into consideration, which is preferably based on an exponential distribution. An availability rate

(25) $\mu =\frac{1}{\mathrm{mttp}}$
is preferably incorporated into the first availability model, in which mttp (mean time to park) indicates the mean time at which vehicles park at the corresponding parking space position P.sub.i. The availability rate therefore corresponds to a rate at which parking spaces become free at the parking space position P.sub.i. Then
p=1−e.sup.−tnμ
is the probability that a parking space will become free with n occupied parking spaces after the time t. Correspondingly, the waiting time until a parking space becomes free with a probability greater than p is

(26) $t=\frac{-\log \left(1-p\right)}{n\mu }.$

(27) If a driver waits, for example, at a parking space position P.sub.i with n=10 occupied parking spaces, which are typically parked on for approximately t=30 minutes, the driver has to wait approximately t=13.82 minutes to find a free parking space with 99% probability. The costs for this waiting time can be specified, for example, by a cost function c.sub.wait(p,j) with 1≤j≤n, wherein c.sub.wait quantifies the costs for waiting at the parking space position P.sub.j until a parking space becomes free with a probability greater than p.

(28) In some cases, it can be promising for the driver to again approach a parking space position P.sub.j which has already been approached. While the costs of again approaching a parking space position P.sub.i from the parking space position P.sub.j are given time-independently by a cost function c.sub.d(i,j,s), wherein s characterizes a state of the vehicle, the availability of free parking spaces at the parking space position P.sub.j changes upon the renewed approach. This availability is therefore also referred to as conditional availability. The time-dependent or conditional availability corresponds to a probability of finding a free parking space upon the renewed approach, after a free parking space was not found upon the prior approach, and can be ascertained on the basis of a second availability model.

(29) A statistical model, with the aid of which the time-dependent or conditional availability can be estimated, is the birth and death process, i.e., a homogeneous Markov process. Two parameters are preferably incorporated in this model: λ is the query rate and characterizes the number of the vehicles which wish to park on the parking space per unit of time, for example per hour, and μ is the availability rate. The probability that a new vehicle arrives at the parking space and that at least one vehicle leaves the parking space is preferably modeled in each case by an exponential distribution.

(30) While the query rate is independent of the number of vehicles which are already parked on parking spaces at the parking space position P.sub.j, the availability rate increases the more parking spaces are occupied. Moreover, the query rate and the availability rate are preferably time-dependent, for example on the time of day or even season. With λ(t) and μ(t) as functions of time, the probabilities for various occupancy states at the parking space position P.sub.i can be described by the following matrix differential equation:

(31) $\left[\begin{array}{c}{\stackrel{.}{P}}_0\\ \mathrm{.Math.}\\ {\stackrel{.}{P}}_i\\ \mathrm{.Math.}\\ {\stackrel{.}{P}}_n\end{array}\right]=\left[\begin{array}{ccccccc}-\lambda & \mu & & & & & \\ & & \ddots & & & & \\ & & \lambda & -\left(\lambda +i\mu \right)& \left(i+1\right)\mu & & \\ & & & & \ddots & & \\ & & & & & \lambda & -n\mu \end{array}\right]\left[\begin{array}{c}{P}_0\\ \mathrm{.Math.}\\ P_i\\ \mathrm{.Math.}\\ P_n\end{array}\right].$

(32) In this case, the diagonal of the matrix contains the entries −λ, . . . , −(λ+iμ), . . . , −nμ. The upper secondary diagonal of the matrix contains in the upper half of the matrix the entries μ, . . . , (i+1)μ, and the lower secondary diagonal of the matrix contains in the lower half of the matrix the entries λ. All other entries are zero. For a start vector p, the equation describes the state of parking spaces or their availability by p(t) in the course of time, if λ(t) and μ(t) are known. Using the matrix A, the equation can be written as {dot over (p)}=Ap with p=[P.sub.0 . . . P.sub.n].sup.T.

(33) Under the assumption that A=const. in a time interval of interest, for example while the vehicle travels from one parking space position P.sub.i to another, already previously approached parking space position P.sub.j, the differential equation can be solved with the aid of a matrix exponential function. For example, the approach p(t)=e.sup.cp.sub.0 with C=A.Math.t can be selected, wherein

(34) $e^C=\stackrel{\infty }{\underset{i=0}{.Math.}}\frac{C^i}{i!}.$
The matrix exponential function is very efficiently available, for example by applying the Padé approximation.

(35) The return to an already previously approached parking space position P.sub.j after a time t correspondingly supplies a probability of finding a free parking space
p(t)=e.sup.A.Math.tp.sub.0
with p.sub.0=(0 . . . 0 1).sup.T. This probability, which corresponds to a time-dependent or conditional availability, can be used to ascertain the optimum sequence with respect to the total travel time, in which at least a part of the at least two different parking space positions P.sub.i are to be approached.

LIST OF REFERENCE SIGNS

(36) 1 device for outputting navigation information 2a, 2b, 2c input interface 3 data processing unit 4 output interface N navigation information L position data Z destination data P parking data P.sub.i,j parking space position p.sub.πi availability P.sub.0 vehicle position F destination position R route P′ parking attempt π strategy