Innovations in Intelligent Transportation Systems and Applications
In this informative content, various aspects of Intelligent Transportation Systems (ITS) are discussed, including safety applications to make drivers aware of unseen hazards, efficiency/convenience/mobility applications for on-route traffic and weather conditions, environmental/energy applications such as ride/car sharing, and spatio-temporal resource search involving mobile agents. The discussion also delves into parking statistics in major cities, highlighting issues such as congestion resulting from cruising for parking, vehicle miles traveled for parking waste, and CO2 emissions. Overall, the content emphasizes the importance of leveraging technology for enhanced transportation solutions.
- Intelligent Transportation Systems
- Safety Applications
- Efficiency
- Environmental Sustainability
- Spatio-Temporal Resource Search
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Computation in Intelligent Transportation Computation in Intelligent Transportation Ouri Wolfson Ouri Wolfson University University of Illinois, Chicago 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 c(v1,s1) v1 s1 Possible cost components: Travel time Walk-time to destination Wait time $-cost Safety Customer destination for taxi Combination of above c(v1,s2) s2 v2 c(v1,sm) . . . . . . . . . vn sm 11
Noncompetitive (Centralized) Model Minimum Total Time Traveled c(v1,s1) v1 s1 0 0 c(v1,s2) 0 0 s2 v2 t s c(v1,sm) . . . . . . 0 0 . . . Theorem: Assignment with minimum total cost can be computed efficiently vn sm Proof: reduction to minimum cost network flow problem. 12
Enter Selfishness 1 s1 5 v1 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 s1 c,t(v1,s2) Nash Equilibrium (NE): No agent can reduce its cost, if all others are rational (attempt to minimize theirs) c,t(v1,s1) s2 v2 c,t(v1,sm) . . . . . . . . . vn 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 w1 > w3 > w2 m3 > m2 > m1 m1 w1 w1 > w2 > w3 m1 > m2 > m3 m2 w2 w2 > w3 > w1 m2 > m1 > m3 m3 w3 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 s1 5 v1 v2 2 s2 8 9/7
Price of Anarchy (SigSpatial11) 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 5 s1 v2 v1 8 2 s2 City_Hall
1 s1 v1 s view of the system v1 2 s2 City_Hall
5 s1 v2 s view of the system v2 8 s2 City_Hall
Greedy strategy 1 5 s1 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 Fishermens Wharf area using SFPark data
Probabilistic information Node Intersection : vi Edge Block: eij Cost of eij: cij (simplified) Probability of finding a resource on eij: pij Cost of quitting on vi: qi
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 5 s1 v2 v1 8 2 s2 City_Hall
Complete Availability-Knowledge vehicles compute and pay equilibrium price. Vehicles are happy City_Hall is still not happy. 1 s1 v2 v1 8 s2 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 s1 5 v1 v2 2 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 (ACMGIS12) 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 vthat 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 5 s1 1 v1 v2 2 8 s2 0
Auction Algorithm Start with an arbitrary assignment 0 5 s1 1 v1 v2 2 8 s2 0
Auction Algorithm v2is not happy since 0.8 > 0.5 0 5 s1 1 v1 v2 2 8 s2 0
Auction Algorithm v2is not happy since 0.8 > 0.5 0 5 s1 1 v1 v2 2 8 s2 Then swap slots with v1. 0
Auction Algorithm 0.15 v2is not happy since 0.8 > 0.5 5 s1 1 v1 v2 2 8 s2 Then swap slots with v1. 0 Raise price of s1 to point where value is same as s2.
Auction Algorithm Now both are happy so we are done. 0.15 5 s1 1 v1 v2 2 8 s2 0
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 5 s1 8 2 s2 City_Hall
Parking Example: Complete Knowledge with Negotiation I ll offer you $2, let me have s1. Ok, I ll take the $2!! 1 5 s1 v2 v1 8 2 s2 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 +$2 5 s1 2 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 5 s1 v2 v1 8 2 s2 City_Hall
