Abstract
Vehicular mobile crowdsensing (MCS) enables many smart cities and urban sensing applications. Managed fleets (such as taxis) can serve as a platform for MCS due to their long operational time and city-scale coverage. The primary goal of these fleets is not sensing, which lead to poor sensing coverage and sensing quality. For example, disadvantaged areas will be rarely covered by taxi fleets. An actuation system is required for MCS to get good (large and balanced) sensing coverage quality. At the same time, this actuation system needs to 1) improve the main mobility goals of the managed fleets and 2) minimize the number of actuation commands due to the scale and human-centric nature of the fleets.
We propose a fleet actuation system that actuates vehicular taxi fleets for optimal sensing coverage quality while matching ride requests with taxis. The system integrates 1) a mobility prediction model that guides the selection of taxis to actuate and 2) a ride request prediction model to help match ride request with taxis, lower incentive cost and improve taxi drivers' motivation. Preliminary simulations show up to 40% improvement in sensing coverage quality improvement while also improving ride requests matching.
The algorithm developed will be deployed with our deployment partner on an electric taxi fleet of 400 taxis. Our deployment partner will help with system development and deployment.
Description
This proposal answers the question: how can we achieve optimal city-wide sensing coverage quality through collaboration while also matching ride requests with taxis?
Introduction
The rapid growth of mobile devices with powerful sensing units has promoted the development of mobile crowdsensing (MCS), in which spatially distributed participants collectively sense and share data. The extracted information from shared data can be used to measure, map, analyze, or estimate any processes of interest for large-scale smart city applications, such as traffic conditions, air pollution, noise level, etc. In smart cities, vehicle fleets, such as traditional taxis and rideshare systems (e.g. Uber, Lyft), enable large-scale sensing with high spatiotemporal coverage and make a future wide-scale smart city and urban sensing applications feasible with minimal infrastructure investment.
Sensing coverage quality, which considers both the area and evenness of data collection, is one of the key performance indices (KPI) of the MCS system that influence the quality of the information collection. However, as non-dedicated sensing platforms, MCS systems using managed fleets such as taxis, need to consider more than the sensing coverage quality. Due to its operational nature, most taxis will gather around busy areas, like a central business district (CBD), while little data are collected in other areas. This is particularly true to disadvantaged neighborhoods, which will lead to underserved communities.
Much past work has been done to improve the coverage quality, such as auction-based or game-theoretical mechanisms [1, 2]. However, these prior approaches rely on a large number of detailed information on participants, which is unreliable, costly, and potentially dangerous for drivers.
It is difficult to optimize sensing coverage quality in a vehicular MCS with a limited budget due to two major challenges: limited effectiveness of actuation given a limited budget, and conflicting goals between the fleet needs and the MCS platform.
1. Low effectiveness on actuation: Given a number of taxis in the same area, it is difficult to decide which ones to actuate for higher sensing coverage quality improvement. This is because for different vehicles in the same area, they have different original intended routes. We do not have to spend our budget actuating taxis who already plan to head to sparse areas, as changing their routes would not significantly affect sensing coverage quality. As a result, actuation effectiveness with the same limited budget will be low. On the contrary, changing routes of taxi drivers who plan to head for busy areas and actuating them to sparse areas improves sensing coverage quality more.
2. Conflicting goals: As a non-dedicated sensing platform, taxis put a high priority on looking for new ride requests, which is usually not consistent with improving sensing coverage quality. Simply actuating taxis with a monetary incentive causes high actuation cost and low motivation. All taxis make individual optimal decisions and tend to stay in busy areas, where they think they will access more ride requests. As a result, the sensing coverage of overall taxis is small and unbalanced. An optimal solution can improve sensing coverage quality by incorporating knowledge about ride requests. For example, if a taxi knows the system will likely guide them to areas where ride requests are more frequent, they are more willing to follow its suggestions.
Proposed Approach
We propose a system that actuates vehicular taxi fleets for optimal sensing coverage quality through the incorporation of matching ride requests with taxis. This means that we will select and actuate drivers based on their locations and predicted route to obtain the maximum sensing improvement if actuated. The proposed system will determine routes for all the available taxis during each actuation period through two main steps.
1. At the start of each actuation period, the system first adopts a mobility prediction model to forecast the near-future taxi destinations. The prediction guides the system to decide which taxis to select for actuation to achieve maximum sensing coverage quality improvement with a given limited budget. The system intends to spend the budget on actuating taxis, which are predicted to head for busy areas, to sparse areas instead. As a result, actuating fewer taxes can bring the same or more sensing quality improvement.
2. We also plan to include a ride request prediction model to predict near-future ride requests across the city. Based on this prediction, the system chooses routes to actuate taxis, which aims to improve the overall sensing coverage quality and match the ride requests with the taxis. This not only lowers the cost of actuation but also improves the motivation for the driver. Since the driver is not only motivated by monetary gains but also with additional rides, they would be more likely to participate.
Utilizing these two key steps, the system sends the actuated routes and corresponding monetary incentives to the selected taxis.
System Overview: To optimize sensing coverage quality as well as match ride requests with taxis, we design our actuation system based on two key observations: 1) The cost of actuating one taxi depends on whether the system can match a taxi with a ride request at the destination. If the system matches the taxi with a ride request, the taxi driver is willing to accept a lower monetary incentive since they can earn money from the new rides [3]. 2) The sensing coverage quality after actuation depends on selecting which taxis to actuate.We do not have to actuate taxis that are already heading to sparse areas, as changing their trajectories would not significantly improve the sensing coverage quality. On the other hand, changing the trajectories of those that plan to head for busy areas and actuating them towards sparse areas can improve sensing coverage quality more.
Figure 1 shows the planned overview of the actuation system. Taxis report their real-time trajectory data and whether they are available for actuation. Unavailability can occur for two reasons: customers already riding in taxis, or drivers' unwillingness to be actuated. The system calculates 1) which taxis to be actuated, 2) where they will be actuated to, and 3) how much monetary incentive they are paid. The results will be sent back to the taxis, thus actuating them to achieve sensing coverage quality optimization and ride request matching.
The Pre-Processing module splits the city into congruent grids with the given spatial resolution. The taxi trajectories' data is also discretized in both the temporal and spatial domains. The outputs of this module are the taxi id, the discretized time index, and the discretized longitude and latitude indices.
The Vehicle Mobility Prediction module, which is trained by the history taxi trajectory data, predicts taxi mobility. The prediction output is fed to the Multi-Incentive Algorithm module to guide the system in wisely selecting which taxis to actuate, which improves the effectiveness of the actuation. The system framework allows different mobility prediction models. For simplicity but without loss of generality, we will adopt a Markov based mobility prediction model.
The Ride Request Prediction module predicts ride requests over the city, which is outputted to the Multi-Incentive Algorithm module. Based on this prediction, the Multi-Incentive Algorithm module selects routes for actuated taxis. The Ride Request Prediction module uses historical ride request data, which can be derived from taxi occupancy data, to train the ride request model. The system framework allows for different ride request prediction models. We plan to explore graph-based ride request prediction models to improve the prediction.
The Monetary Incentive Calculation module calculates the incentive based on the selected routes from the Multi-Incentive Algorithm module and the prediction from the Ride Request Prediction module. The results are sent back to the Multi-Incentive Algorithm module for further optimization.
The Multi-Incentive Algorithm module selects the taxis to be actuated based on predictions from the Vehicle Mobility Prediction module and designs trajectories for those taxis based on the Ride Request Prediction. In addition, both the taxi and trajectory selection is decided by the individual monetary incentives of each taxis obtained from Monetary Reward Calculation. If multiple taxis or trajectories achieve the same sensing coverage quality improvement, the Multi-Incentive Algorithm module selects the one with the lowest monetary incentive.
The system will be evaluated using existing New York and Beijing data traces, as well as deployed as described in the deployment Plan.
References:
1. Yang, D., Xue, G., Fang, X., & Tang, J. (2016). Incentive mechanisms for crowdsensing: Crowdsourcing with smartphones. Biological Cybernetics, 24(3), 1732-1744.
2. Zhao, D., Li, X. Y., & Ma, H. (2014, April). How to crowdsource tasks truthfully without sacrificing utility: Online incentive mechanisms with budget constraint. In INFOCOM, 2014 Proceedings IEEE (pp. 1213-1221). IEEE.
3. Zhang, X., Yang, Z., Sun, W., Liu, Y., Tang, S., Xing, K., & Mao, X. (2016). Incentives for mobile crowd sensing: A survey. IEEE Communications Surveys & Tutorials, 18(1), 54-67.
4. Xu, X., Chen, X., Liu, X., Noh, H. Y., Zhang, P., & Zhang, L. (2016, November). Gotcha II: Deployment of a Vehicle-based Environmental Sensing System. In Proceedings of the 14th ACM Conference on Embedded Network Sensor Systems CD-ROM (pp. 376-377). ACM.
Timeline
• Quarter 1: Develop initial brute force algorithm for incorporate the mobility model and incentive model base incorporation. Develop the theoretical problem framework.
• Quarter 2: Implement algorithm Simulate results from existing NYC and Beijing taxi traces.
• Quarter 3: Develop near-optimal non-exhaustive results to improve scalability and trace and actuation generation speed.
• Quarter 4: Deploy new algorithm on physical taxi hardware in Shenzhen. Utilizing air pollution as the motivating application
Strategic Description / RD&T
Deployment Plan
To evaluate our actuation system on optimizing sensing coverage quality and matching ride requests, we will utilize our taxi deployment in the city of Shenzhen China. We design a mobile sensing hardware platform for city-scale air pollution data collection. We deploy the sensing hardware on the 400 electric taxis in Shenzhen China, which covers roughly 2000 square kilometers. We will particularly focus on a number of suburban areas, as well as the CBD to evaluate the system in different focus areas of study. Currently, we have deployed the sensing hardware on 29 taxis running for the past year.
Once the route information is determined, it is communicated to the driver. We plan to show this using the existing routing system that is currently used by our deployment taxi fleet partners (Based on Baidu maps). The driver will use our app that receives the map and shows the driver the desired route. For experimental purposes, we will initially rely on existing manual notification mechanism through dispatch to notify taxis to be actuated.
For simplicity but without loss of generality, we will focus on deriving CO pollution map. This is because deriving pollution map for gases are similar and CO is identified as a key air pollutant by both US National Ambient Air Quality Standards (NAAQS) and Chinese Ministry of Environmental Protection.
Expected Outcomes/Impacts
We expect to use the air pollution sensing application as a demonstration application for the actuation system. We plan to apply spatial resolution of 500m by 500m for air pollution monitoring, which correlates to block level scale. We set the temporal resolution as 1 hour, which is the same as most course government-run monitoring stations. The result is expected to be a deployed algorithm on the up to 400 taxis and evaluated on the metrics of a combination of sensing coverage and evenness (i.e. coverage quality).
Expected Outputs
TRID
Individuals Involved
| Email |
Name |
Affiliation |
Role |
Position |
| noh@cmu.edu |
Noh, Hae Young |
CEE |
Co-PI |
Faculty - Untenured, Tenure Track |
| peizhang@cmu.edu |
Zhang, Pei |
ECE/SV |
PI |
Faculty - Untenured, Tenure Track |
Budget
Amount of UTC Funds Awarded
$90000.00
Total Project Budget (from all funding sources)
$90000.00
Documents
| Type |
Name |
Uploaded |
| Data Management Plan |
data_management.pdf |
Jan. 14, 2018, 9:13 a.m. |
| Publication |
SPIE_ilocus_Susu_1.pdf |
March 31, 2019, 1:22 p.m. |
| Presentation |
spie.pptx |
March 31, 2019, 1:22 p.m. |
| Progress Report |
182_Progress_Report_2019-03-30 |
March 31, 2019, 1:22 p.m. |
| Publication |
08712442_Uik0buI.pdf |
Sept. 30, 2019, 3:43 p.m. |
| Publication |
p19-chen.pdf |
Sept. 30, 2019, 3:43 p.m. |
| Presentation |
p19-chen_nEGZ1yH.pdf |
Sept. 30, 2019, 3:43 p.m. |
| Progress Report |
182_Progress_Report_2019-09-30 |
Sept. 30, 2019, 3:43 p.m. |
| Final Report |
182_-_Final_Report.pdf |
Jan. 2, 2020, 8:42 a.m. |
| Publication |
Incentivizing vehicular crowdsensing system for large scale smart city applications. |
Dec. 8, 2020, 9:55 a.m. |
| Publication |
Pas: Prediction-based actuation system for city-scale ridesharing vehicular mobile crowdsensing |
April 19, 2021, 7:52 a.m. |
Match Sources
No match sources!
Partners
| Name |
Type |
| Tsinghua University |
Deployment Partner Deployment Partner |
