Transcript Computation in Intelligent Transportation

Computation in Intelligent Transportation
Ouri Wolfson
University of Illinois, Chicago
1
IGERT Ph.D. program in
Computational Transportation Science
Information Technology
Transportation
• Focus on Intelligent Transportation Systems (ITS)
2
ITS: safety applications
• Make a driver aware of unseen hazards
• Examples:
– Vehicle in front has a malfunctioning brake light
– Vehicle on crossroad is about to run a red light
– Patch of ice at milepost 305
– A vehicle 100 meters ahead has emergency braked
3
3
ITS: Efficiency/convenience/mobility
applications
• On-route traffic and weather conditions,
– What is the average speed a mile ahead of me?
– Is the upcoming pavement wet there?
– Are wipers/fog-lights on there?
– Are there any accidents ahead?
• Resource search
4
4
ITS: Environmental/Energy applications
• Ride/car sharing
• Multimodal routing/navigation for optimal
– Pollution generation/exposure
– Energy consumption
• Persuasive/green technologies
5
Spatio-temporal Resource Search
• Mobile agents (vehicles)
• Static, serially reusable, resources in geo-space or time
•
•
•
•
•
•
•
Parking slots,
Electric-car charging stations
Taxi-cab customers
Bikes at stations
Bike-Station-slots
Package for pick-up/delivery
Airport landing time-slots
• Agents compete for resources
• First agent reaching resource (or closest) captures it
Parking Statistics
• (Shoup 2005) In major cities cruising for parking
generates
• 30% of congestion
• 1,825 vehicle miles traveled/year/slot
• Chicago has over 35,000 curbside parking slots
• 63M Vehicle-Miles-Traveled/year for parking
• waste of over 3.1 million gallons of gasoline
• > 48,000 tons of CO2 emissions
Parking Applications
• SFPark: Smartphone app that
displays location of available
parking slots
• Enabled by sensors in
pavement
8
SFPark Problems
• Safety concern
• Driver distraction
• Solution: Automatic selection and
guidance to slot
• Which parking slot?
• Cost
• Install:
$300/sensor
• Maintain: $170/year
• Solution: smart-phones crowdsourcing
9
Outline of Talk
• Finding spatio-temporal resources
• Models of the problem
• Noncompetitive (Optimality)
• Competitive
(Equilibrium)
• Agents’ availability-information
•
•
•
•
Zero
Incomplete
Probabilistic
Deterministic, complete
• Extensions: pricing, negotiation, truthfulness
• Detecting spatio-temporal resources
• A crowdsourcing approach using smartphones
• Preliminary work on: Transportation  Neuroscience
10
Noncompetitive (Centralized) Model –
Minimum Total Cost
v1
c(v1,s1)
s1
c(v1,s2)
s2
v2
.
.
.
vn
c(v1,sm)
.
.
.
.
.
.
sm
Possible cost components:
• Travel time
• Walk-time to destination
• Wait time
• $-cost
• Safety
• Customer destination for
taxi
• Combination of above
11
Noncompetitive (Centralized) Model –
Minimum Total Time Traveled
v1
0
0
s
0
c(v1,s1)
c(v1,s2)
s2
v2
.
.
.
vn
s1
c(v1,sm)
.
.
.
.
.
.
sm
0
0
t
0
Theorem:
Assignment with minimum
total cost can be computed
efficiently
Proof: reduction to minimum
cost network flow problem.
12
Enter Selfishness
1
v1
s1
5
v2
2
s2
8
System Optimal:
V1->S2 and V2->S1 at total-time 7;
but V1 can improve time
Nash Equilibrium:
V1->S1 and V2->S2 at total-time 9;
V1 and V2 cannot unilaterally improve time
13
Equilibrium
• In real world cars compete for parking
• In selfish parking, i.e. no central authority, Nash
equilibrium is settle-on strategy
v1
v2
.
.
.
vn
c,t(v1,s1)
c,t(v1,s2)
s1
s2
c,t(v1,sm)
.
.
.
.
.
.
Nash Equilibrium (NE): No agent can
reduce its cost, if all others are
rational (attempt to minimize theirs)
sm
Theorem 1: NE assignment can be computed efficiently
• Generally not unique
• Unique if Costs = TravelTimes
14
How compute NE?
Using Stable Marriage Problem
A matching (paring) such that: There doesn’t exist a
man-woman pair from different marriages that prefer
each other over their assigned “spouse”.
Can be solved efficiently (Gale-Shapley 1962)
Men Preference Order
Women Preference Order
m1
w1 > w3 > w2
w1
m3 > m 2 > m 1
m2
w1 > w2 > w3
w2
m1 > m 2 > m 3
m3
w2 > w3 > w1
w3
m2 > m 1 > m 3
15
Resource-Search  Stable-Marriage
• Theorem 2: If
• Each agent ranks the resources increasingly by their costs, and
• Each resource ranks the agents increasingly by their travel-time,
• then:
Solution to the stable marriage problem =>
Nash Equilibrium matching
16
Price of anarchy: Ratio Between
Optimum and Equilibrium
1
v1
s1
5
v2
2
s2
9/7
8
Price of Anarchy (SigSpatial’11)
Proposition 3:
Worst case Price of Anarchy is unbounded
Proof:
1
s1
5
v1
v2
2
s2
1000
18
Resource-Availability information of agents
• Map only
• Incomplete availability-knowledge
• Probabilistic-availability knowledge
• Complete availability-knowledge
Parking Example: Map only
s1
v1
v2
s2
Parking Example: Map only
• Result? Vehicles wander around until coming
upon some available slot. No one is happy.
s1
v2
v1
s2
City_Hall
Incomplete Knowledge: SFPark
• Vehicles:
– Are aware of locations of the slots.
– Are not aware of locations of other vehicles.
1
s1
5
v2
v1
2
s2
8
City_Hall
1
s1
v1’s view of
the system
v1
2
s2
City_Hall
s1
5
v2’s view of
the system
v2
s2
8
City_Hall
Greedy strategy
1
s1
5
v2
v1
s2
Result: v1 is happy but no one else is happy.
v2 and City_Hall are happier but still not happy.
City_Hall
Alternative to Greedy: Gravitational
• Slots have gravitational pull on the vehicles.
– F(v,s) = 1/cost(v,s)2
Compute force vector for
each slot
Add vectors
s2
s1
Move in direction of
resultant vector
(magnitude irrelevant)
s3
v
s4
Repeat
26
Force field generated by Gravitational
strategy
• Vehicles will eventually converge to a slot.
Motion vector changes
depending on:
•
location of vehicle
•
available slots
Motion not directed to a
specific slot
27
Greedy vs. Gravitational in Fishermen’s Wharf
area using SFPark data
Probabilistic information
• Node – Intersection : vi
• Edge – Block: eij
Cost of eij:
cij
Probability of finding a resource on eij: pij
Cost of quitting on vi:
qi
(simplified)
Probabilistic formulation of search
• Find the path of time < T, which has either:
• highest probability of finding a resource
• meaningless if T is very large,
• All infinite paths have probability 1
• lowest expected cost of finding a resource.
• Find the path (possibly infinite) which has minimum
expected cost
Results in Probabilistic model
• Proposition: Expected cost of infinite path is bounded.
• Representation of infinite path: next(i) at each node i;
• Efficient algorithm to find path (maybe infinite) of min expected
cost
• Distinction in the algorithm between 2 types of resources.
• Suppose no resource on edge e with probability pe is found at time t:
• the probability of e at t+1 is still pe (taxi cab customer)
• the probability of e at t+1 is 0 and recovers to pe within a limited amount of time
(parking slot)
Complete Availability-Knowledge
My position
is…
My position
is…
1
s1
5
v2
v1
2
s2
8
City_Hall
Complete Availability-Knowledge
• vehicles compute and pay equilibrium price.
• Vehicles are happy
• City_Hall is still not happy.
1
s1
v2
v1
s2
8
City_Hall
Alternative view of
Complete Availability-Knowledge
• Each agent a knows the future availability of resources; and
• a pursues the lowest-cost resource r that will stay available by the
time a reaches r (not the same as greedy)
How to make City Hall happy?
1
s1
5
v1
v2
2
s2
8
optimum allocation: travel time 7
Pricing by central-authority
10 cents
1
v1
5
v2
2
•
•
•
•
s1
s2
8
Suppose parking at S1 has a price of 10 cents1
Driving 1 minute has a total $-cost of 5 cents
Then it becomes beneficial for V1 to drive to S2
Pricing converts Equilibrium to Optimum
Pricing Scheme (ACMGIS’12)
Pricing for slots, such that:
Priced Equilibrium
is
(unpriced) Cost Optimum
Assuming some conversion $ <-> time
Auction Algorithm
• Start with prices of all slots at 0 and with an arbitrary assignment.
• A vehicle is said to be “happy” if he doesn’t want to change to
another slot given the current costs.
• An iterative process starts:
– For any vehicle v that is “not happy”
• Give v his most preferred slot and swap with its current owner.
• Raise price of this slot to the point where its value to v is the same as its 2nd
preferred slot.
– Repeat Process until everyone is happy.
Auction Algorithm
0
1
s1
5
v1
v2
2
s2
0
8
Auction Algorithm
Start with an arbitrary
assignment
0
1
s1
5
v1
v2
2
s2
0
8
Auction Algorithm
v2 is “not happy”
since 0.8 > 0.5
0
1
s1
5
v1
v2
2
s2
0
8
Auction Algorithm
v2 is “not happy”
since 0.8 > 0.5
0
1
s1
5
v1
v2
2
s2
0
8
Then swap slots
with v1.
Auction Algorithm
0.15
1
s1
v2 is “not happy”
since 0.8 > 0.5
5
v1
v2
2
s2
0
8
Then swap slots
with v1.
Raise price of s1 to
point where value
is same as s2.
Auction Algorithm
Now both are
“happy” so we are
done.
0.15
1
s1
5
v1
v2
2
s2
0
8
But
• V1 pays more than would have paid in equilibrium
and
• The scheme constitutes an additional tax
Complete Availability-Knowledge with Negotiation
• Situation in which the vehicles are aware of:
– locations of the slots.
– locations of other vehicles
• Vehicles can trade slots for $.
– Say $1 = 1min of travel time.
1
s1
2
s2
5
8
City_Hall
Parking Example: Complete
Knowledge with Negotiation
I’ll offer you $2, let me
have s1.
Ok, I’ll take the
$2!!
1
s1
5
v2
v1
2
s2
8
City_Hall
Complete Knowledge with
Negotiation
v2 pays $2 to v1 for s1:
v1 pays cost 0
v2 pays cost 7. Each vehicle pays < its price at equilibrium.
City_Hall is happy .
+$2
s1
2
-$2
5
s2
City_Hall
Guaranteed-Improvement Theorem (GIT)
(SigSpatial’12)
for every configuration of slots and vehicles
there is a payment scheme, and
an optimal allocation (of vehicles to slots) scheme
such that
the cost of each vehicle v (including payment/refund)
≤
than v’s cost in equilibrium (w/o payment)
Truthfulness
v1 and v2 have an incentive to spoof their
location to be the location of s1.
I’m only 0.1 minutes
away from s1.
Ok, then I won’t
even go there.
1
s1
5
v2
v1
2
s2
8
City_Hall
Truthfulness-promotion: Tamper-resistant approach
(1)
Truthfulness-promotion: Fine-Approach (2)
If do not arrive at resource at expected time: heavy fine
Similar to fines in speeding:
may get away offending sometimes,
but when caught pay heavy price.
Truthfulness-promotion:
Pricing-approach (3)
(Transportation Research Part B)
• Use VCG second-price auction to ensure
truthfulness
• Downside: GIT theorem no longer holds
Outline of Talk
• Matching spatio-temporal resources
– Models of the problem
• Noncompetitive (Optimality)
• Competitive
(Equilibrium)
– Levels of information
• Zero
algorithm: random walk
• Incomplete algorithms: greedy, gravitational
• Probabilistic algorithms: min expected cost, max
probability
• Deterministic, complete
– Extensions: pricing, truthfulness
• Detecting spatio-temporal resources
– A crowdsourcing approach using smartphones
54
Parking Availability Map
• Detect when and where a traveler parks/deparks
her car using smartphone sensors
(GPS, accelerometer).
• Create probabilistic-map of parking availability.
University of Illinois (Chicago)
Slot Detection by sensors or by
Parking Status-Detectors
(MDM’12, MDM’13)
Detect parking/deparking activities by
• observing transportation mode transitions.
– parking: car ->
– deparking: walk ->
stationary -> walk
stationary -> car
• Motion patterns associated with parking
(e.g. reverse)
• Pay-by-Phone piggyback
• Acoustic detectors (car door closing, engine
starting)
• Detect: Walk-To-PayBox, Pay, Walk-Back
Image source:
http://www.clipartheaven.com
University of Illinois (Chicago)
Combining status-detectors for real-time signals
• IWCTS 2014
Historical Availability Profile (HAP)
Time period
9:00am10:00am
10:00am11:00am
11:00am12:00pm
12:00pm
-1:00pm
Historical mean
availability
1
3
2
4
Example profile for a street block (partial)
Challenges
• Initial low sample rate
– 1%-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) construction
• 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
b  (1  fn)
fp: false positive probability
fn: false negative probability
Justification:
1. Each report (statistically) corresponds to 1/b actual parkings
2. 1/(1fn) reports should have been received if there were no false negatives
3. The report is correct with 1fp probability
• Similarly when a deparking report is received
Theorem
Assume that fp=0. For any  if NumberOfSamples -> ∞, then:
Prob{| qˆ (t )  q(t ) |  }  1
HAP Estimation average
True average
More specifically:
Cumulative distribution function of the standard 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
HAP Experiments using SFPark data
April 10 – August 11, 2012
• Root-Mean-Square-Error of a block on Chestnut St (4 parking
slots), assuming 1% penetration ratio
0.57
RMSE of estimated mean
0.56
0.55
0.54
0.53
0.52
0.51
0.5
0.49
0.48
0.47
fn=fp=0
fn=fp=0.05 fn=fp=0.1 fn=fp=0.15 fn=fp=0.2 fn=fp=0.25
Combining real-time signals with historical
availability
historical statistics
parking availability
estimator (PAE)
parking availability
estimates
parking status
detector (PSD)
parking status
detector (PSD)
parking status
detector (PSD)
Combining HAP and real-time observations for
Boolean-availability
boolean availability accuracy
0.8
0.75
0.7
WA
KF
0.65
SPP
0.6
HS
0.55
0.5
fn=fp=0.05
fn=fp=0.15
fn=fp=0.25
Speculative relationship:
transportation  neuroscience
Big data in the human brain
• 100 billion neurons
• 100 trillion synapses
• A neuron can fire 5 - 50 times every second.
Structural connectome
• Graph representing neurons and synapses
• Currently, rather than neurons, nodes represent brain regions
(voxels)
– Edges have weights, representing the number of synapses between
corresponding voxels
Billions of structural connectomes
• Connectome of a person changes over time
• Connectomes of different persons are different
Functional connectome
• Graph representing correlation between pairs of
neurons/voxels
– Time series representing the activity of nodes m and n are .2
correlated
• Person specific
• Task specific
Other species
• C-elegans: worm for which the structural connectome has
been mapped at the neuron level
• About 280 neurons (nodes of the structural connectome)
Mobile big data
• Structural connectome: Road network
• Functional connectome: signals = vehicles, or mobile objects
– Signals propagate from neuron to neuron, i.e. “travel”
• No GPS
• Signals “merge”
Currently studying
• Is the flow of signals in the brain closer to a
– System Optimum or User Equilibrium
Traffic assignment in transportation
– Given:
• Road network (supply)
• Origin-destination matrix (demand)
– Calculate equilibrium or optimum traffic assignment which gives for
each link:
• Flow
• Density,
• Travel-time
Transportation in Connectomics
• Structural connectome:
– Weighted graph representing the wiring between brain voxels
– Interpretation: supply of traffic means
• Functional connectome (task specific)
– Weighted graph representing the correlation between brain voxels
– Interpretation: Demand for signals traffic
• Which traffic assignment (SO or UE) better represents the flow
of signals in the connectome?
Conclusion
• Matching spatio-temporal resources
– Models of the problem
• Noncompetitive (Optimality)
• Competitive
(Equilibrium)
– Agents’ availability-information
•
•
•
•
Zero
Incomplete algorithms: greedy, gravitational
Probabilistic algorithms: min expected cost, max probability
Deterministic, complete
– Extensions: pricing, truthfulness
• Detecting spatio-temporal resources
– A crowdsourcing approach using smartphones
• Statistical analysis to determine availability
75