Report

Real time street parking availability estimation Dr. Xu, Prof. Wolfson, Prof. Yang, Stenneth, Prof. Yu University of Illinois, Chicago • In one business district, vehicles searching for parking produces 730 tons of CO2, 47000 gallons on gasoline, and 38 trips around the world. 2 Problem • estimating street parking availability using only mobile phones • mobile phone distribution among drivers • GPS errors, transportation mode detection errors, Bluetooth errors, etc. 3 Motivations • • • • save time and gas to find parking reduce congestion and pollution mobile phone are ubiquitous affordable - SF park 8000 parking spaces cost 23M USD • external sensors such as cameras not utilized 4 Why mobile phones ? • ubiquitous with several sensors (GPS, gyro, accelerometer) • several people own a mobile phone • other alternatives – Sensor in pavement (e.g. SF Park) $300 + $12 per month – Manual reporting (e.g. Google OpenSpot) – Ultrasonic sensors on taxi (e.g. ParkNet) $400 per sensor 5 Contributions • parking status detection (PSD) • street parking estimation algorithms – historical availability profile construction (HAP) – parking availability estimation (PAE) • • • • weighted average (WA) Kalman Filter (KF) historical statistics (HS) scaled PhonePark (SPP) 6 PSD, HAP, PAE 7 Parking status detection (PSD) • Determine when/where a driver park/deparks Image sources: http://videos.nj.com/, http://pocketnow.com/smartphone-news/ http://sf.streetsblog.org 8 Parking Status Detection (PSD) • We proposed three schemes for PSD – transportation mode transition of driver – Bluetooth pairing of phone and car – Pay by phone piggyback 9 3 Schemes for PSD Transportation mode transition (GPS/accelerometer) Bluetooth Pay-by-phone piggy back 10 HAP construction • estimates the historic mean (i.e.(t)) and variance (i.e. (t)) of parking • relevant terms – prohibited period, permitted period – false positives, false negatives – b, N 11 Why is Building Profile Non-trivial • Low sample rate due to low market penetration – 1% to 5% • Errors in parking status detection – False negative • Missing parking activities that have occurred • E.g., misclassifying parking as getting off a bus – False positive: • Reporting parking activities that have not occurred • E.g., misclassify getting on a bus as deparking Historical availability profile (HAP) Algorithm • Start with a time at which the street block is fully available, e.g., end of a prohibited time interval (start permitted period) • When a parking report is received, availability is reduced by: b: penetration ratio (uniform distribution) 1 fp fp: false positive probability b (1 fn ) fn: false negative probability Justification: 1. Each report (statistically) corresponds to 1/b actual parking 2. 1/(1fn) reports should have been received if there were no false negatives 3. The report is correct with 1fp probability • Similarly when a deparking report is received HAP algorithm PP1 PP2 PPm m qˆ ( t ) m aˆ i ( t ) i 1 m Qˆ ( t ) 2 ( aˆ i ( t ) qˆ ( t )) i 1 m 14 HAP uncertainty bounding • Given an error tolerance, with what P the diff between q(t) and (t) is less than x parking spaces. • Lemma 1 • Lemma 2 15 More specifically: Cumulative distribution function of normal distr. Prob {| qˆ ( t ) q ( t ) | } 2 ( Estimation average True average m ) 1 Qˆ ( t ) Estimation variance • Example: – If we want error < 2 with 90% confidence, • standard deviation of the estimation is 10 (i.e., the average fluctuation of estimated availability at the 8:00am is 10). – then we need 68 permitted periods. • i.e. about two months of data. Number of samples , or permitted periods Parking Availability Estimation (PAE) • Solely real time observations – scaled PhonePark (SPP) – capped • Solely historical parking data (HAP) – historical statistics (HS) (t) = (t) 17 Parking Availability Estimation (PAE) • Combining history with real time – Weighted average (t) = (t) + 1 − (t) RMSE of estimated mean 1 0.9 b=1%, fn=fp=0, Chestnut 0.8 b=1%, fn=fp=0.1, Chestnut 0.7 b=50%, fn=fp=0, Polk 0.6 b=50%, fn=fp=0.1, Polk 0.5 0.4 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 b=50%, fn=fp=0.25, Polk wHS 18 Parking Availability Estimation (PAE) • combining history with real time – Kalman Filter estimation (KF) (t) = .(t) +() + .(t) +() 19 Evaluation • RT data from SFPark.org 04/10 to 08/11 • Polk St (12 spaces )and Chestnut St (4 spaces ) 20 HAP Results • RMSE between q(t) (t) • b = 1% , see for b = 50% in paper Polk St. block 12 spaces available Chestnut St. block 4 spaces available 21 PAE results • RMSE between x(t) (t) • b =1 % , see for b = 50% in paper 2.5 0.54 2 WA 1.5 KF SPP 1 HS 0.5 RMSE of estimated availability RMSE of estimated availability 0.53 0.52 0.51 WA 0.5 0.49 KF 0.48 SPP 0.47 HS 0.46 0.45 0 0.44 fn=fp=0.05 fn=fp=0.15 fn=fp=0.25 fn=fp=0.05 fn=fp=0.15 fn=fp=0.25 22 PAE results • Boolean availability i.e. at least one slot available • b =1 % 0.8 0.95 0.85 0.8 WA 0.75 KF 0.7 SPP 0.65 HS 0.6 boolean availability accuracy boolean availability accuracy 0.9 0.75 0.7 WA 0.65 KF SPP 0.6 HS 0.55 0.55 0.5 0.5 fn=fp=0.05 fn=fp=0.15 fn=fp=0.25 fn=fp=0.05 fn=fp=0.15 fn=fp=0.25 23 Related work • ParkNet • SFPark.org project $400 per system for each vehicle $300 per sensor + $12 per month service. Project cost $23 million • Google’s OpenSpot Cumbersome Image sources: http://www.thesavvyboomer.com/ http://pocketnow.com/smartphone-news/ http://sf.streetsblog.org 27 Conclusion • schemes for parking status detection (PSD) – GPS, accelerometer, Bluetooth • historical availability profile (HAP) algorithm • real time parking availability estimation algorithms (PAE) 25 Acknowledgements • SF Park team (J. Primus etc.) • Reviewers for fruitful comments • NSF and NURAIL 26