Method for optimizing run curve of vehicles

• US 8,938,348 B2
• Filed: 12/13/2011
• Issued: 01/20/2015
• Est. Priority Date: 12/13/2011
• Status: Active Grant

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Nikovski, Daniel, Lidicky, Bernard
• Primary Examiner(s): Dager, Jonathan M
• Application Number:
  US13/324,075
• Publication Number:
  US 20130151107A1
• Time in Patent Office: 1,134 Days
• Field of Search: None
• US Class Current: 701/99
• CPC Class Codes: B61L 2210/04 Magnetic elevation vehicles [maglev]
• CPC Class Codes: B61L 27/16 Trackside optimisation of vehicle or train operation
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G05B 13/024 in which a parameter or coefficient is automatically adjusted to optimise the performance

Abstract

A method determines a run-curve of a motion of a vehicle as a function of at least a speed of the vehicle and a position of the vehicle in a continuous space. First, the method determines Markov decision process (MDP) with respect to a set of anchor states selected from the continuous space, such that a control moving the vehicle to a state transitions the MDP to an anchor state with a probability determined as a function of a distance between the anchor state and the state in the continuous space, and solves the MDP subject to constraints to determine an MDP policy optimizing a cost function representing a cost of the motion of the vehicle. Next, the method determines the run-curve based on the MDP policy.

Claims

1. A method for determining a run-curve of a motion of a vehicle during a trip along a route as a function of at least a velocity of the vehicle and a position of the vehicle in a continuous space of the trip, comprising steps of:

determining a Markov decision process (MDP) with respect to a set of anchor states selected from the continuous space, such that a control moving the vehicle to a state transitions the MDP to an anchor state with a probability determined as a function of a distance between the anchor state and the state in the continuous space, wherein the determining the MDP comprises;

partitioning a traveled distance of the vehicle in a set of periods of distances forming a set of stages in the continuous space;

determining a step of the transition as a period of distance, such that each control transition the system from a previous state of a previous stage to a next state on a next stage; and

selecting the set of anchor states such that a location of each anchor state in the continuous space is on a stage from the set of stages;

solving the MDP subject to constraints to determine an MDP policy optimizing a cost function representing a cost of the motion of the vehicle; and

determining the run-curve based on the MDP policy, wherein at least some of the steps are performed in a processor of the vehicle.

2. The method of claim 1, wherein the constraints include one or combination of a legal constraint, a constraint of the route and a constraint of the vehicle.

3. The method of claim 1, wherein the cost function represents energy consumption of the vehicle during the trip, such that the run-curve optimizes the energy consumption of the vehicle during the trip.

4. The method of claim 1, wherein the cost function represents both energy consumption of the vehicle during the trip and a total time of the trip, such that the run-curve optimizes a combination of energy consumption of the vehicle and a total time of the trip.

5. The method of claim 1, wherein the cost function represents energy consumption of the vehicle during a predetermined time of a trip, such that the run-curve optimizes the energy consumption of the vehicle during the predetermined time of the trip.

6. The method of claim 1, wherein the determining the run-curve based on the MDP policy uses a method selected from a group consisting of a nearest anchor point method, a largest vote method, and a highest expected merit method.

7. The method of claim 1, wherein the determining the MDP comprises:

determining a simplex enclosing the state in the continuous space, wherein vertices of the simplex are formed by a subset of the set of anchor states; and

determining the probability of transitioning the MDP from the anchor state to each anchor state in the subset as barycentric coordinates of a location of the state within the simplex.

8. The method of claim 1, wherein the run-curve is further a function of a traveled time, further comprising:

partitioning the traveled time in a set of periods of times forming a set of time slices in the continuous space, such that each control transitions the system from the previous state in a previous time slice to the next state in a next time slice;

sampling the continuous space to determine the set of anchor states, such that each anchor state is located in a time slice, wherein each time slice includes at least one anchor state, such that each control transitions the MDP from the anchor state in the previous time slice to the next anchor state in the next time slice;

determining a simplex enclosing the state in the next time slice, wherein vertices of the simplex are formed by a subset of the set of anchor states in the next time slice;

determining the probability of transitioning the MDP from the anchor state to each anchor state in the subset as barycentric coordinates of the location of the state within the simplex; and

assigning the probability of transitioning the MDP from the anchor state to the next anchor state not forming the subset as equal to zero.

9. A method for determining an optimal sequence of controls transitioning a system from an initial state to a final state in a continuous space defined by state variables of the system, wherein the optimal sequence is monotonically increasing over at least one state variable, wherein the system is a dynamic system having states defined by a dynamic function of previous states and a discrete set of controls, wherein, for each transition, a control is selected from the discrete set of controls, such that, for each control, the dynamic function transitions the system from a previous state to a next state over a step of transition, wherein the system includes a vehicle, such that the optimal sequence of controls determines a run-curve of a motion of the vehicle during a trip, comprising:

determining Markov decision process (MDP) with respect to a set of anchor states selected from the continuous space, such that each control from the discrete set of controls transitions the MDP from an anchor state to a next anchor state with a probability determined based on a location of the next anchor state in the continuous space with respect to a location of a state in the continuous space, in which the dynamic function of the anchor state and a corresponding control transitions the system;

solving the MDP to determine an optimal policy for the MDP defining an optimal control for each anchor state; and

determining the optimal sequence of controls in the continuous space based on the optimal policy, wherein the state variables include a speed of the vehicle and a traveled distance of the vehicle, wherein the traveled distance is bound by a beginning of the distance corresponding to the initial state and an end of the distance corresponding to the final state, wherein the speed of the vehicle is bound by legal constraints, and wherein the control is bound by mechanical constraints of the system, and, wherein at least some of the steps of the method are performed by a processor of the vehicle.

10. The method of claim 9, wherein the set of anchor states forms a set of simplexes, such that vertices of each simplex are defined by corresponding anchor states, further comprising:

assigning the probability of transitioning the MDP from the anchor state to the next anchor equals zero, if the next anchor state does not form a simplex enclosing the state in the continuous space; and

otherwise

determining the probability of transitioning the MDP from the anchor state to the next anchor as a convex decomposition of the location of the state with respect to the location of the next anchor state.

11. The method of claim 9, further comprising:

applying Delaunay triangulation to the set of anchor states to produce a set of simplexes;

determining a simplex enclosing the state in the continuous space; and

determining the probability of transitioning the MDP from the anchor state to each anchor state in the subset as barycentric coordinates of the location of the state within the simplex.

12. The method of claim 9, further comprising:

determining the step of the transition as a period of time, such that a set of periods of time forms a travel time for which the means of transportation travels over the traveled distance.

13. The method of claim 9, further comprising:

determining the step of the transition as a period of distance, such that a set of periods of distances forms the traveled distance.

14. The method of claim 9, wherein the determining the optimal sequence of controls further comprises:

selecting an optimal control for each state in the continuous state based on an optimal control of a nearest anchor state defined by the optimal policy.

15. The method of claim 9, wherein the determining the optimal sequence of controls further comprises:

selecting an optimal control for each state in the continuous state based on optimal controls of a subset of anchor states forming a simplex enclosing the state, wherein the an optimal control of each anchor state in the subset is scaled based on corresponding barycentric coordinates of the location of the state within the simplex.

16. The method of claim 9, wherein the determining the optimal sequence of controls further comprises:

determining, for each state in the continuous state, a subset of anchor states forming a simplex enclosing the state;

determining, based on the optimal policy, a value of each control at each anchor state in the subset;

determining a combined value of each control as a sum of corresponding controls scaled based on corresponding barycentric coordinates of the location of the state within the simplex; and

selecting, for each state in the continuous state, an optimal control having highest corresponding combined value.

17. A method for determining a run-curve of a motion of a vehicle during a trip along a route as a function of at least a velocity of the vehicle and a position of the vehicle in a continuous space of the trip, comprising steps of:

determining a Markov decision process (MDP) with respect to a set of anchor states selected from the continuous space, such that a control moving the vehicle to a state transitions the MDP to an anchor state with a probability determined as a function of a distance between the anchor state and the state in the continuous space, wherein the run-curve is a function of a traveled time, wherein the determining comprises;

partitioning the traveled time in a set of periods of times forming a set of time slices in the continuous space, such that each control transitions the system from the previous state in a previous time slice to the next state in a next time slice;

sampling the continuous space to determine the set of anchor states, such that each anchor state is located in a time slice, wherein each time slice includes at least one anchor state, such that each control transitions the MDP from the anchor state in the previous time slice to the next anchor state in the next time slice;

determining a simplex enclosing the state in the next time slice, wherein vertices of the simplex are formed by a subset of the set of anchor states in the next time slice;

determining the probability of transitioning the MDP from the anchor state to each anchor state in the subset as barycentric coordinates of the location of the state within the simplex; and

assigning the probability of transitioning the MDP from the anchor state to the next anchor state not forming the subset as equal to zero;

solving the MDP subject to constraints to determine an MDP policy optimizing a cost function representing a cost of the motion of the vehicle; and

determining the run-curve based on the MDP policy, wherein at least some of the steps are performed in a processor of the vehicle.