# US 2022/0036261 A1 · Method and system for dynamically predicting vehicle arrival time using a temporal difference learning technique

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2022/0036261 A1
- Document ID: US20220036261A1
- Status: Published application
- Kind: A1
- Application number: 17/216,493
- Filed: 2021-03-29
- Published: 2022-02-03
- Earliest claimed: 2020-07-24
- Assignees: Tata Consultancy Services Limited
- Applicants: Tata Consultancy Services Limited
- Inventors: Avinash Achar; Vignesh Lakshmanan Kangadharan Palani Radja; Sanjay Bhat
- Web page: https://patentgrep.com/patent/US20220036261A1

## CPC

- 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)
- G06Q 10/0631: Resource planning, allocation, distributing or scheduling for enterprises or organisations
- G06N 3/047: Probabilistic or stochastic networks
- G06N 3/0499: Feedforward networks
- G06N 3/08: Learning methods
- G06N 3/09: Supervised learning
- G06N 3/092: Reinforcement learning
- G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks
- G06N 20/00: Machine learning
- G06Q 50/40: Business processes related to the transportation industry (shipping G06Q10/083)
- G08G 1/0112: {from the vehicle, e.g. floating car data [FCD]}
- G08G 1/0129: {for creating historical data or processing based on historical data}
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G08G: TRAFFIC CONTROL SYSTEMS (guiding railway traffic, ensuring the safety of railway traffic B61L; arrangement of road signs or traffic signals E01F9/00; radar or analogous systems, sonar systems, lidar systems specially adapted for traffic control G01S13/91, G01S15/88, G01S17/88; {radar or analogous systems, sonar systems, lidar systems specially adapted for anti-collision purposes G01S13/93, G01S15/93, G01S17/93})

## Abstract

This disclosure relates generally to a method and system for dynamically predicting vehicle arrival time using a temporal difference learning technique. Due to varying uncertainties predicting vehicle arrival time and travel time are crucial elements to make the public transport travel more attractive and reliable with increased traffic volumes. The method includes receiving a plurality of inputs in real time and then extracting a plurality of temporal events from a closest candidate trip pattern using a historical database. Further, a trained temporal difference predictor model (TTDPM) is utilized for dynamically predicting the arrival time from the current location of the vehicle to the target destination based on the plurality of nonlinear features. The non-linear features and linear approximator formulation of TTDPM provides fast gradient computation improves training time. Additionally, updating the revised state information at every iteration provides better accuracy of arrival time prediction in real time.

## Claims

### Claim 1

A processor (104) implemented method for dynamically predicting a vehicle arrival time comprising:
receiving (302), via one or more hardware processors (104), a plurality of inputs comprising a current status of a vehicle, a target destination of the vehicle comprising a plurality of route segments associated with a trip, and an elapsed time of the vehicle from a source location of the trip to a current location of the vehicle, wherein the current status of the vehicle comprises the current location of the vehicle for a given time instance;
fetching (304), via the one or more hardware processors(104), a plurality of trip patterns for the plurality of inputs using a historical database, wherein each trip pattern from the plurality of trip patterns is a possible closest candidate trip that runs from the current location of the vehicle to the target destination;
extracting (306), via the one or more hardware processors (104), a plurality of temporal events, from at least one trip pattern from the plurality of trip patterns,
wherein the at least one trip pattern has similarly matches with the current location of the vehicle to the target destination,
wherein the plurality of temporal events comprises a trip travel time (Tpv) for a day is based on the most recent vehicle travelled during the same day of the trip and a trip travel time (Tpw) for a week is based on the plurality of vehicles travelled during a particular time interval;
constructing (308), via the one or more hardware processors, a markov reward process model using the current location of the vehicle for the given time instance and the elapsed time of the vehicle from the source location of the trip to the current location of the vehicle;
obtaining (310), via the one or more hardware processors (104), a plurality of nonlinear features from the plurality of temporal events and the plurality of inputs using a 3-layer feed forward multilayer network which is based on a monte carlo process; and
dynamically predicting (312), using a trained temporal difference predictor model (TTDPM) enabled by the markov reward process model executed by the one or more hardware processors (104), the arrival time from the current location of the vehicle to the target destination based on the plurality of nonlinear features serving as an input to the trained temporal difference predictor model (TTDPM).

### Claim 2 (depends on 1)

The method as claimed in claim 1, wherein dynamically predicting the arrival time from the current location of the vehicle to the target destination based on the plurality of nonlinear features using the trained temporal difference predictor model (TTDPM) comprises:
obtaining, the plurality of nonlinear features from the plurality of temporal events and the plurality of inputs using the 3-layer feed forward multilayer network which is based on the monte carlo process;
randomly initializing one or more weight vectors;
arbitrarily selecting a learning rate;
initializing an eligibility vector to zeros;
iteratively performing for every iteration:
computing,
(i) the eligibility vector, using a previous iteration of an estimated eligibility vector with a (λ) parameter, wherein variation in the (λ) parameter is from the continuous range of predictors and a gradient of value function, and wherein the gradient of value function is a replicate value of the plurality of nonlinear features, and
(ii) one step temporal difference error using a bootstrapped target estimate and a pre-estimated value function at current state,
wherein the bootstrapped target estimate is based on the current state reward associated with the markov reward process, which is the travel time from the current state which is the current location of the vehicle to the next state which is the next route segment of the trip summed with the preestimated value function at the next state associated with the markov reward process model, and
wherein the preestimated value function at next state is estimated using the next state which is the next route segment of the trip, and
update, the one or more weight vectors based on the revised state by,
(i) computing, a weight value based on the product of arbitrarily selected learning rate with the one-step temporal difference error and the eligibility vector, and
(ii) summing, the value of current iteration weight vector with the weight value.

### Claim 3 (depends on 2)

The method as claimed in claim 2, wherein the one step temporal difference error is a difference between the bootstrapped target estimate and the pre-estimated value function at the current state.

### Claim 4 (depends on 1)

The method as claimed in claim 1, constructing the markov reward process model comprises:
generating, a state using the plurality of inputs and the plurality of temporal events;
dynamically regenerating, a revised state, when the current location of the vehicle is traversed from the current route segment to the next route segment within the target destination of the trip; and
assigning, a reward value from the reward engine for the revised state transition of the vehicle traversed.

### Claim 5

A system (100), for dynamically predicting a vehicle arrival time comprising:
a memory (102) storing instructions;
one or more communication interfaces (106); and
one or more hardware processors (104) coupled to the memory (102) via the one or more communication interfaces (106), wherein the one or more hardware processors (104) are configured by the instructions to:
receive, a plurality of inputs comprising a current status of a vehicle, a target destination of the vehicle comprising a plurality of route segments associated with a trip, and an elapsed time of the vehicle from a source location of the trip to a current location of the vehicle, wherein the current status of the vehicle comprises the current location of the vehicle for a given time instance;
fetch, a plurality of trip patterns for the plurality of inputs using a historical database, wherein each trip pattern from the plurality of trip patterns is a possible closest candidate trip that runs from the current location of the vehicle to the target destination;
extract, a plurality of temporal events, from at least one trip pattern from the plurality of trip patterns,
wherein the at least one trip pattern has similarly matches with the current location of the vehicle to the target destination,
wherein the plurality of temporal events comprises a trip travel time (Tpv) for a day is based on the most recent vehicle travelled during the same day of the trip and a trip travel time (Tpw) for a week is based on the plurality of vehicles travelled during a particular time interval;
construct, a markov reward process model using the current location of the vehicle for the given time instance and the elapsed time of the vehicle from the source location of the trip to the current location of the vehicle;
obtain, a plurality of nonlinear features from the plurality of temporal events and the plurality of inputs using a 3-layer feed forward multilayer network which is based on a monte carlo process; and
dynamically predict using a trained temporal difference predictor model (TTDPM) enabled by the markov reward process, the arrival time from the current location of the vehicle to the target destination based on the plurality of nonlinear features serving as an input to the trained temporal difference predictor model (TTDPM).

### Claim 6 (depends on 5)

The system (100) as claimed in claim 5, wherein dynamically predicting the arrival time from the current location of the vehicle to the target destination based on the plurality of nonlinear features using the trained temporal difference predictor model (TTDPM) comprises:
obtain, the plurality of nonlinear features from the plurality of temporal events and the plurality of inputs using the 3-layer feed forward multilayer network which is based on the monte carlo process;
randomly initializing one or more weight vectors;
arbitrarily select a learning rate;
initialize an eligibility vector to zeros;
iteratively perform for every iteration:
compute,
(i) the eligibility vector, using a previous iteration of an estimated eligibility vector with a (λ) parameter, wherein variation in the (λ) parameter is from the continuous range of predictors and a gradient of value function, and wherein the gradient of value function is a replicate value of the plurality of nonlinear features, and
(ii) one step temporal difference error using a bootstrapped target estimate and a pre-estimated value function at current state,
wherein the bootstrapped target estimate is based on the current state reward associated with the markov reward process, which is the travel time from the current state which is the current location of the vehicle to the next state which is the next route segment of the trip summed with the preestimated value function at the next state associated with the markov reward process, and
wherein the preestimated value function at next state is estimated using the next state which is the next route segment of the trip, and
update, the one or more weight vectors based on the revised state by,
(i) computing, a weight value based on the product of arbitrarily selected learning rate with the one-step temporal difference error and the eligibility vector, and
(ii) summing, the value of current iteration weight vector with the weight value.

### Claim 7 (depends on 6)

The system (100) as claimed in claim 6, wherein the one step temporal difference error is a difference between the bootstrapped target estimate and the pre-estimated value function at the current state.

### Claim 8 (depends on 5)

The system (100) as claimed in claim 5, constructing the markov reward process model comprises:
generating, a state using the plurality of inputs and the plurality of temporal events;
dynamically regenerating, a revised state, when the current location of the vehicle is traversed from the current route segment to the next route segment within the target destination of the trip; and
assigning, a reward value from the reward engine for the revised state transition of the vehicle traversed.

### Claim 9

One or more non-transitory machine-readable information storage mediums comprising one or more instructions which when executed by one or more hardware processors perform actions comprising:
receiving, a plurality of inputs comprising a current status of a vehicle, a target destination of the vehicle comprising a plurality of route segments associated with a trip, and an elapsed time of the vehicle from a source location of the trip to a current location of the vehicle, wherein the current status of the vehicle comprises the current location of the vehicle for a given time instance;
fetching, a plurality of trip patterns for the plurality of inputs using a historical database, wherein each trip pattern from the plurality of trip patterns is a possible closest candidate trip that runs from the current location of the vehicle to the target destination;
extracting, a plurality of temporal events, from at least one trip pattern from the plurality of trip patterns,
wherein the at least one trip pattern has similarly matches with the current location of the vehicle to the target destination,
wherein the plurality of temporal events comprises a trip travel time (Tpv) for a day is based on the most recent vehicle travelled during the same day of the trip and a trip travel time (Tpw) for a week is based on the plurality of vehicles travelled during a particular time interval;
constructing, a markov reward process model using the current location of the vehicle for the given time instance and the elapsed time of the vehicle from the source location of the trip to the current location of the vehicle;
obtaining, a plurality of nonlinear features from the plurality of temporal events and the plurality of inputs using a 3-layer feed forward multilayer network which is based on a monte carlo process; and
dynamically predicting, using a trained temporal difference predictor model (TTDPM) enabled by the markov reward process model the arrival time from the current location of the vehicle to the target destination based on the plurality of nonlinear features serving as an input to the trained temporal difference predictor model (TTDPM).

### Claim 10 (depends on 9)

The one or more non-transitory machine-readable information storage mediums of claim 9, wherein dynamically predicting the arrival time from the current location of the vehicle to the target destination based on the plurality of nonlinear features using the trained temporal difference predictor model (TTDPM) comprises:
obtaining, the plurality of nonlinear features from the plurality of temporal events and the plurality of inputs using the 3-layer feed forward multilayer network which is based on the monte carlo process;
randomly initializing one or more weight vectors;
arbitrarily selecting a learning rate;
initializing an eligibility vector to zeros;
iteratively performing for every iteration:
computing,
(iii) the eligibility vector, using a previous iteration of an estimated eligibility vector with a (λ) parameter, wherein variation in the (λ) parameter is from the continuous range of predictors and a gradient of value function, and wherein the gradient of value function is a replicate value of the plurality of nonlinear features, and
(iv) one step temporal difference error using a bootstrapped target estimate and a pre-estimated value function at current state,
wherein the bootstrapped target estimate is based on the current state reward associated with the markov reward process, which is the travel time from the current state which is the current location of the vehicle to the next state which is the next route segment of the trip summed with the preestimated value function at the next state associated with the markov reward process model, and
wherein the preestimated value function at next state is estimated using the next state which is the next route segment of the trip, and
update, the one or more weight vectors based on the revised state by,
(iii) computing, a weight value based on the product of arbitrarily selected learning rate with the one-step temporal difference error and the eligibility vector, and
(iv) summing, the value of current iteration weight vector with the weight value.

### Claim 11 (depends on 10)

The one or more non-transitory machine-readable information storage mediums of claim 10, wherein the one step temporal difference error is a difference between the bootstrapped target estimate and the pre-estimated value function at the current state.

### Claim 12 (depends on 9)

The one or more non-transitory machine-readable information storage mediums of claim 9, constructing the markov reward process model comprises:
generating, a state using the plurality of inputs and the plurality of temporal events;
dynamically regenerating, a revised state, when the current location of the vehicle is traversed from the current route segment to the next route segment within the target destination of the trip; and
assigning, a reward value from the reward engine for the revised state transition of the vehicle traversed.