System and method for generating an occupancy model

• US 9,070,093 B2
• Filed: 04/03/2012
• Issued: 06/30/2015
• Est. Priority Date: 04/03/2012
• Status: Active Grant

• Current Assignee: Conduent Business Services, LLC (Conduent, Inc.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Grbovic, Mihajlo, Zoeter, Onno R., Dance, Christopher R., Bouchard, Guillaume, Guo, Shengbo
• Primary Examiner(s): Kim, Eunhee
• Application Number:
  US13/438,313
• Publication Number:
  US 20130262059A1
• Time in Patent Office: 1,183 Days
• Field of Search: 703/2, 703/6, 701/533, 706/12
• US Class Current: 1/1
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• CPC Class Codes: G08G 1/14 indicating individual free spaces in parking areas

Abstract

A system and method for generating an occupancy model are disclosed. The model is learned using occupancy data for zones, each zone including cells, which are occupied or not at a given time, each with a sensor, which may be reporting or not. The data provides an observed occupancy corresponding to a number of cells in the respective zone which have reporting sensors, and the number of those sensors which are reporting that the respective cell is occupied. The occupancy model is based on a demand model and a sensor noise model which accounts for behavior of the non-reporting sensors. The noise model assumes that the probability of a sensor being in the reporting state is dependent on whether the respective cell is occupied or not. The model can fit the occupancy data better than one which assumes that non-reporting cells are occupied with the same frequency as reporting ones.

Claims

1. A computer implemented method comprising:

receiving occupancy data for each of a plurality of zones, each zone comprising a respective set of cells and including a sensor for each of the cells in the set of cells, each of the cells being in one of a plurality of occupancy states at a time, the occupancy states including an occupied state and an unoccupied state, each of the sensors being in only one of a reporting state, in which the sensor reports the occupancy state of the respective cell, and a non-reporting state, in which the sensor does not report the occupancy state of the cell, at a time, the occupancy data comprising, for each of a plurality of times;

an observed occupancy, which is based on a number of cells in the respective zone that are reported by the sensors to be in the occupied state, and

a number of the sensors in the respective zone that are in the reporting state, at least one of the sensors of at least some of the zones being in the non-reporting state for at least one of the plurality of times;

with a processor, learning at least one predictive occupancy model configured for predicting an occupancy of at least one of the zones, the learning being based on at least a portion of the received occupancy data, at least one of the at least one predictive occupancy models including a sensor noise model which assumes that a probability of a sensor being in the reporting state is dependent on whether the respective cell is in the occupied state.

2. The method of claim 1, wherein the at least one occupancy model comprises a plurality of predictive occupancy models, each of the plurality of occupancy models comprising a respective different noise model.

3. The method of claim 2, further comprising evaluating the plurality of predictive occupancy models to identify one of the plurality of predictive occupancy models which best fits at least a portion of the received occupancy data.

4. The method of claim 1, wherein the occupancy model comprises at least one noise model selected from the group consisting of:

a noise model which assumes that the probability of a sensor being in the reporting state is independent of whether the respective cell is in the occupied state;

a noise model which assumes that the probability of a sensor being in the reporting state is dependent on a time parameter;

a noise model which assumes that the probability of a sensor being in the reporting state is dependent on location parameter;

a noise model which assumes that the probability of a sensor being in the reporting state is dependent on latent parameter selected from a finite set of latent parameters; and

combinations thereof.

5. The method of claim 1, wherein the occupancy model further comprises a demand model which predicts occupancy of each zone as a function of a capacity of the zone and an occupancy rate, the capacity of each zone being based on a total number of the cells in the respective set of cells.

6. The method of claim 5, wherein the demand model assumes that a Poisson distribution relates the predicted occupancy of each zone to the capacity of the zone and the occupancy rate.

7. The method of claim 5, wherein the learning comprises learning the demand model and the sensor noise model together in an iterative process.

8. The method of claim 5, wherein the learning comprises optimizing a log-likelihood function of parameters of the occupancy model in an iterative process.

9. The method of claim 1, wherein the learning includes learning parameters of the occupancy model, the parameters include at least one occupancy rate.

10. The method of claim 1, wherein the learning includes learning parameters of the occupancy model, the parameters including probability parameters, the probability parameters including a probability that a sensor is reporting if the respective cell is occupied, and a probability that a sensor is reporting if the respective is unoccupied.

11. The method of claim 10, wherein the probability parameters include for each of a plurality of times, a probability that a sensor is reporting if the respective cell is occupied, and a probability that a sensor is reporting if the respective cell is unoccupied.

12. The method of claim 11, wherein the probability parameters include for each of a plurality of times, a probability that a sensor is reporting if the respective cell is occupied, and a probability that a sensor is reporting if the respective cell is unoccupied.

13. The method of claim 11, wherein the probability parameters include for each of a plurality of locations, a probability that a sensor is reporting if the respective cell is occupied, and a probability that a sensor is reporting if the respective cell is unoccupied.

14. The method of claim 11, wherein the probability parameters include for each of a plurality of latent types, a probability that a sensor is reporting if the respective cell is occupied, and a probability that a sensor is reporting if the respective cell is unoccupied.

15. The method of claim 1, further comprising at least one of:

a) receiving current occupancy data and predicting an actual occupancy of at least one of the zones with the learned occupancy model;

b) predicting occupancy of at least one of the zones at each of a plurality of times with the learned occupancy model and establishing a pricing schedule for the at least one zone based on the predicted occupancies; and

c) where the at least one occupancy model comprises a plurality of occupancy models, identifying a failure hypothesis based on identifying one of the occupancy models which best fits the occupancy data; and

d) comparing predicted occupancy output by the occupancy model with other occupancy-related data for the cells of at least one of the zones.

16. The method of claim 1, wherein the predicted occupancy of the zone includes a predicted occupancy of cells in the at least one zone which have a sensor in the non-reporting state.

17. The method of claim 1, wherein the zones comprise parking zones and the cells comprise parking spaces which are in the occupied state when occupied by a vehicle.

18. A computer program product comprising a non-transitory recording medium storing instructions, which when executed on a computer causes the computer to perform the method of claim 1.

19. A system comprising memory storing instructions for performing the method of claim 1, and a processor in communication with the memory which implements the instructions.

20. The method of claim 1, wherein for each zone each of the respective set of cells is sized to receive only a single vehicle.

21. An occupancy prediction system comprising:

memory which receives occupancy data for each of a plurality of zones, each zone comprising a respective set of cells and including a sensor for each of the cells in the set of cells, each of the cells being in one of an occupied state and an unoccupied state at a time, each of the sensors being in one of a reporting state, in which the sensor reports the occupancy state of the respective cell, and a non-reporting state, in which the sensor does not report the occupancy state of the cell, at a time, the occupancy data comprising;

an observed occupancy, which is based on a number of cells in the respective zone that are reported to be in the occupied state, and

a number of the sensors in the respective zone that are in the reporting state;

at least one occupancy model stored in memory which is configured for predicting occupancy of at least one of the zones, the predicted occupancy including a predicted occupancy of cells in the at least one zone which have a sensor in the non-reporting state, each of the at least one occupancy models being based on;

a demand model which predicts occupancy of each zone as a function of a capacity of the zone and an occupancy rate, the capacity of each zone being based on a total number of the cells in the respective set of cells; and

a respective sensor noise model, at least one of the sensor noise models assuming that a probability of a sensor being in the reporting state is dependent on whether the respective cell is in the occupied state or the unoccupied state.

22. The system of claim 21, wherein the at least one occupancy model comprises a plurality of occupancy models.

23. The system of claim 22, further comprising a model testing component for testing the plurality of occupancy models on occupancy data to identify one of the models which best fits the data.

24. The system of claim 23, further comprising a model learning component for learning the at least one occupancy model using occupancy data for the zones at a plurality of times.

25. A computer implemented method comprising:

providing at least one occupancy model which is configured for predicting occupancy of at least one of a plurality of zones, each zone comprising a respective set of cells and including a sensor for each of the cells in the set of cells, each of the cells being in one of an occupied state and an unoccupied state at a time, each of the sensors being in one of a reporting state and a non-reporting state at a time, the predicted occupancy including a predicted occupancy of cells in the at least one zone which have a sensor in the non-reporting state, each of the at least one occupancy models being based on a demand model and a respective sensor noise model jointly learned from prior occupancy data acquired for the at least one zone, at least one of the noise models assuming that a probability of a sensor being in the reporting state is dependent on whether the respective cell is in the occupied state, the demand model predicting occupancy of each zone as a function of a capacity of the zone and an occupancy rate, the capacity of each zone being based on a total number of the cells in the respective set of cells;

with a computer system, receiving current occupancy data for at least one of the plurality of zones, the current and prior occupancy data comprising;

an observed occupancy, which is based on a number of cells in the respective zone that are reported to be in the occupied state, and

a number of the sensors in the respective zone that are in the reporting state, wherein at least one of the sensors is in the non-reporting state and the occupancy state of the at least one sensor in the non-reporting state is not known by the computer system; and

with a processor of the computer system, predicting an occupancy of the at least one of the zones using at least one of the at least one occupancy models.