Data based node penalties
View Patent ↗A method for determining a node based penalty for use in a path finding algorithm for an automated material handling system (AMHS) is described. The AMHS includes a track interconnecting a plurality of nodes, and on which a plurality of material transport vehicles (MTVs) move. In particular, each of the nodes and MTVs provide queue-blocking data that is stored in a queue-blocking database along with a time tag indicating the time the data was collected. The AMHS retrieves data from the queue-blocking database that has a time tag within a predetermined time window and determines a queue blocking metric for each node in the material transport system. The queue blocking time is converted from to a node based penalty that is the additional distance that an MTV would travel while blocked. Thus, the node based penalty distance is added to the physical distance between a pair of nodes to provide a distance metric indicative of the current traffic conditions. The AMHS receives a source node and a destination node from a material control system and determines all possible routes between the two nodes. The distance metric for each route is computed and the AMHS selects the route having the shortest distance metric.
1. A method for determining a node based penalty in a material transport system having a plurality of interconnected nodes, the method comprising the steps of:
providing a plurality of data from the plurality of nodes indicative of the queue blocking time of the corresponding node;
windowing the plurality of data over a predetermined time period; and
determining a node penalty metric indicative of the queue blocking time during the window period for each of the plurality of nodes having windowed data associated therewith.
2. The method of claim 1 wherein the step of determining the node penalty metric indicative of the queue blocking time includes determining the average queue blocking time.
3. The method of claim 1 wherein the step of determining the node penalty metric indicative of the queue blocking time includes converting queue blocking time into a node penalty distance.
4. The method of claim 1 wherein the step of providing a plurality of data from the plurality of nodes indicative of the queue blocking time of the corresponding node includes receiving from each of the plurality nodes storing queue blocking data to a database along with time data indicative of the time the data was taken.
5. The method of claim 4 wherein the step of windowing the plurality of data over a predetermined time period includes selecting from the plurality of queue blocking data stored in the database having time data within the predetermined window time period.
6. A method of selecting a route from a source node to a destination node from among a plurality of identified routes, each route including one or more intermediate nodes connecting the source node and the destination node, the method comprising:
receiving from each of the plurality nodes queue blocking data;
storing the received queue blocking data associated with each of the plurality of nodes in a database along with time data indicative of the time the data was collected;
selecting from the plurality of queue blocking data stored in the database having time data within a predetermined window time period;
determining the average queue blocking time for each of the plurality of nodes;
converting the queue blocking time into a node penalty distance;
determining for each of the plurality of routes the distance between the source node and the destination node as a function of the actual distance to be traveled and the node penalty distance associated with each intermediate node in each of the plurality of routes.
7. The method of claim 6 wherein the step of determining for each of the plurality of routes the distance between the source node and the destination node includes calculating the distance between the source node and the destination node according to
Dist
(
Node
Source
,
Node
Dest
)
=
∑
i
=
2
M
(
Dist
(
i
-
1
,
i
)
+
Node_Penalty
(
i
)
*
(
MTV
queue
+
1
)
)
.
8. The method of claim 7 wherein the Node_Penalty(j) is
1
K
*
K
(
∑
k
=
1
Qj
,
k
)
*
C
,
where K is the total number of data contained in the current time window, Q j,k is the k th queue blocking data where k=1,2,3, . . . K for node j and C is the conversion factor between time and distance.