Hello everyone! I would like to present our work
Dynamic Public Resource Allocation Based on Human Mobility Prediction.
This is Sijie Ruan from Xidian University in China.
Public resources, such as billboards, trash bins, and surveillance cameras
are deployed by companies or governments for different purposes.
The goal of the allocation of those resources can be roughly summarized as
covering as many people as possible with limited resources,
which has been extensively studied in previous years.
However, due to the nature of human mobility,
the crowd distribution is highly uneven on both spatial and temporal domains.
As a result, redundant resources have to be deployed to guarantee the desired crowd coverage.
The figure shows the spatial distribution of trash bins as well as crowds over a day
at Happy Valley (a popular theme park in Beijing).
It is clear that the trash bins marked with rectangles are not always in service.
The right figure shows the utilization of 95 trash bins during the whole day,
where 70%-80% trash bins are not fully utilized.
Apart from non-data driven static deployment,
the dynamic of crowd flows is also another important factor leading to such low utilization.
Based on these observations, a natural question arises:
is it possible to serve more people with fewer resources, if these resources are mobile?
Fortunately, with the rapid development of the robotic systems,
various unmanned vehicles emerge for logistics or transportation purposes.
Furthermore, some companies, like JD.com, are developing the common mobile bases
that can carry any payload, which can make the resource mobile.
However, it is still a non-trivial task to design effective scheduling
for these dynamic public resources (or mobile agents) :
The first reason is that our resources are limited due to budget constraints,
so that we can not cover all area at all times.
The second reason is that the mobile agents have energy constraints.
If we always move to the maximal coverage locations of each timestamp,
the energy would be used up easily.
The third reason is that the action space is large.
A mobile agent can move to any location in a region,
and a location can also be served by any agent.
Computing an optimal solution is extremely time consuming.
To overcome the first two challenges, we first perform a multi-step crowd flow prediction
so that we can have a better understanding of future dynamics of crowd flow distribution,
then we propose the multi-agent long-term maximal coverage scheduling problem,
which schedules multiple mobile agents based on the prediction results
to collaboratively maximize the crowd coverage during the service time of a day
while considering the energy limitation of each agent.
To further tackle the third challenge, we propose a heuristic algorithm
Energy Adaptive Scheduling (EADS) to schedule mobile agents efficiently and effectively.
In our problem setting, the service area is discretized into uniform grid locations,
and each grid location has a crowd flow reading dynamically changing with respect to time.
We also have K homogenous agents, each of which has the same energy limitation.
Each agent has a service radius, which indicates the size of coverage area in its neighborhood.
The crowd flows in a grid location are covered if there is at least one agent can serve the grid.
There is a static charge station in the region,
and all agents must start and terminate their trips at the station.
Then the problem is defined as follows:
Based on the predicted crowd flows until the end of the service time,
which can be obtained using existing methods,
we calculate the visiting location sequence of agents so that
the daily crowd coverage is maximized without using up the energy of each individual agent.
Knowing the long-term prediction would never be accurate enough,
we apply the Model Predictive Control (MPC) strategy.
There would be several decision time during the service time.
When a decision time arrives, based on the real time observed crow flows,
the future crowd flows are predicted.
Then the problem would be solved again based on the most fresh crowd flow predictions
and the current location and remaining energy of each agent.
And only the first future location assignment of each agent is actually used.
Given the NP-hardness of the problem,
we propose the two-step heuristic algorithm Energy Adaptive Scheduling to solve it efficiently.
The first step is Multi-Level Max Cover Scheduling,
which tries to find a schedule to visit the maximal k coverage locations at each step
so that the energy of each agent would not be used up.
If such a schedule cannot be found, we execute the second step Energy-Aware Scheduling,
The main idea is that we first initialize a policy that agents are sent to locations that maximizes
the coverage of averaged future crowd flows, and fixed at those locations in the future,
Then a hill-climbing based algorithm is applied to improve the current policy.
We evaluate our proposed method on real-world gridded crowd flow datasets
in Beijing Happy Valley.
We also collect the locations of trash bins in the park by on-field investigation.
We calculate the number of resources required of different methods
to meet the same average daily crowd coverage of the current deployment.
EADS achieves 80.0% and 56.8% resource reduction with respect to
the current and the static maximal coverage deployment strategies, respectively.
Thanks for your attention. Our data and codes are publicly available.