|Title of Invention||
A METHOD FOR JOURNEY SEQUENCE PLANNING OF A LIFT INSTALLATION AND A DESTINATION CALL CONTROL SYSTEM
|Abstract||The present invention relates to an apparatus for detennining the optimal travel i sequence for an elevator installation includes smart tenninals sending destination specific travel requests and other planning infonnation to a job manager for each elevator car. The job managers perfonn a situation-based search process to detennine the optimal travel sequence plan for the associated elevator and submit an offer to the tenninal sending the travel request. The tenninal compares offers and books a selected one. The job managers are responsive to relevant changes in the situation upon which the plan is based for detennining a changed actual travel sequence and associated changed offer.|
Destination call control for lifts
The invention relates to a destination call control for lifts according to the definitions of the patent claims.
In known manner a lift control serves the purpose of serving cage calls to the various storeys of the building. The drive of the lift knows as commands merely the instructions 'travel upwardly', 'travel downwardly', 'door open' and 'door close'.
In larger buildings usually a group of two to eight lifts is installed, from which it is now necessary to select that lift which appears the most suitable for a newly input cage call from a storey, a so-termed storey call. As a rule this is the lift which has the shortest travel path to this storey. If, however, each lift of the group has to serve, on this travel path, other storey calls beforehand, then passengers will board at the storeys, the destination of whom is known only when they have pressed the corresponding cage buttons. The allocation of a storey call to a lift thus becomes problematic, since permanent uncertainty about the destinations to be travelled to exists.
Accordingly, in the lift industry numerous experiments can be observed to skilfully 'guess' the possible destination storeys of the passengers by means of use of learning methods on the basis of neuronal networks or genetic algorithms. The effect of such a method is, however, very limited, because merely coarse traffic patterns, such as, for example, the morning upward peak, are identifiable with any certainty. However, it remains unclear what a passenger wants when, for example, he or she calls a lift on a Monday morning about 10.37 o'clock at the 10th storey of a high-rise office.
Another starting point for solution of the control problem consists of so-called destination call controls. With a destination call control the passengers, before boarding a lift or a lift cage, input their desired destination storey, for example by way of a keyboard similar to a telephone, i.e. a so-termed terminal. The boarding storey is known to the destination call control from the position of the terminal. After input of the destination storey, an allocation algorithm of the control ascertains that lift of the lift group which enables the quickest and most comfortable transport for the passenger to his or her destination. The terminal indicates to the passenger this lift of the group of lifts and the passenger can step into the correspondingly marked lift at his or her own pace. If the lift stops for boarding, then the
destination of the passenger is confirmed, for example, by way of a display device in ine door frame. In the cage itself, there are no longer present any knobs for input of destinations. In this manner, through use of a destination call control, passengers with an identical transport destination can be grouped and thereby the transport performance of the lift system increased.
An example, which is known from EP 0 699 617 A1, of such a destination call control is, in addition, in the position of identifying individual passengers. For each identified passenger additional data with respect to boarding position and disembarking position, the passenger space requirement and possible additional service requirements are taken into consideration, by access to a data memory, in the determination of the optimal transport possibility.
This and other conventional destination call controls are based on an intuitive approximation algorithm on the basis of allocation rules. This allocation algorithm is designed and programmed in each instance specifically to requirement. In the case of a journey request, i.e. the destination call, the data related to persons and the installation and detected by way of an appropriate sensor system are passed on to the allocation algorithm and run through the algorithm for determination of the journey sequence.
If new additional journey requests arise during execution of a journey sequence, then the already computed journey sequence is modified to that effect. In that case, however, only simple modifications can be undertaken, which can have the consequence that only a modified journey sequence which is related to destination call and which is no longer the optimal journey sequence with respect to the changed preconditions is executed. Long waiting times and/or transport times for the passengers can result therefrom. Moreover, interrelationships of individual control options, so-termed service requirements, are not always expressed logically and in unbroken manner in such a fixedly programmed allocation algorithm. Moreover the control software created in requirement-specific form for computation of the journey sequence is regarded as detailed and complicated. It is disadvantageous, in particular, that a once-created allocation algorithm can be subsequently adapted to different customer-specific control requirements only with substantial cost. In practice, for adaptation to changed service requirements a new lift-specific allocation algorithm has to be prepared in each case and implemented in entirety.
destination calls, and the booking of the transport requests, i.e. so-termed jobs, to the respectively selected lift. The terminals receive from the central job manager as a response the identification of the selected lift, which they thereupon display (for example 'A' or'B').
The communication between the terminals and the lifts is simple to organise, because all communication runs by way of a central control, i.e. the central job manager. The organisation of the jobs takes place at a central job manager in a waiting queue, a so-termed 'first in, first out' data structure. This organisation is simple and secures a clear running sequence.
In the case of the central concept the terminals only have to process the destination call input of the passenger as well as the indication of the lift booked by the central job manager and require for this purpose only simple software. The use of simple and economic terminals makes this possible.
In the case of a decentral construction of the job manager, the terminals are connected by way of a capable communications network with the job managers of the individual lifts of a lift group. The terminals directly ask the job managers of the individual lifts for a transport offer for the respectively registered destination call. The terminals independently collect these offers, compare them and determine the optimal booking of the passenger. In the case of a decentral job manager the organisation of the jobs takes place in parallel for several jobs, wherein a desired superimposition of enquiries and bookings is possible.
Further advantages of the decentral concept of the destination call control reside in the -by comparison with the central concept - faster reaction of the job manager to enquiries, an increased stability of the overall system due to the decentralisation and a simplified architecture of the job manager, since a separate central control does not have to be provided.
Insofar as the decentral embodiment is provided, the terminals are equipped with intelligent booking software. The communication between the terminals and the job managers of the individual lifts is preferably carried out by way of use of contract network protocols. The job managers of the individual lifts are themselves in a position to organise jobs in parallel and to correctly manage their status.
The central and decentral concept of the job manager can also be combined with one another in a destination call control. Any number of job managers, which control one or more lifts, can be present in a network.
According to a particularly preferred development of the invention the situation-based destination call control is represented as a multi-agent system, which realises the entire controls of installation, wherein the planning system is an agent in this multi-agent system. The lift installation can comprise any number of lifts with any layout. Thus, several lifts can also co-operate with a different number of decks in one group, i.e. a so-termed heterogeneous multi-decker group.
The construction as a multi-agent system enables a modular implementation of the destination call control, in which individual components, i.e. the so-termed agents, for example planning system, doors, drive and taxi driver, can be exchanged as desired without the entire system having to be changed.
An event-controlled activation of the agents in a multi-agent system makes the system substantially more robust relative to occurring errors. If, for example, a shaft door at a storey breaks down due to a faulty contact, then either the job manager can cause an evacuation travel or, however, the taxi driver can initially allow the still-present plan to be executed. For further passenger enquiries, the fault can be communicated to the configuration manager which informs all relevant components of the system that temporarily this storey cannot be served by this lift. A failure of components does not signify immediate failure of the entire system as long as the safety of the passengers is guaranteed.
Further advantageous refinements of the invention are contained in the independent claims.
Embodiments of the invention in which the destination call control is constructed as a multi-agent system for organisation of the traffic of a lift installation are illustrated in the drawing and explained in more detail in the following, in which:
Fig. 1 shows, schematically, the construction of a first embodiment of the
destination call control with a decentral job manager for the control of an individual lift;
Fig. 2 shows a schematic illustration of the organisation of a pool of requested
and offered jobs in a destination call control with a decentral job manager for control of a group of lifts;
Fig. 3 shows an instantaneous state description according to the first
Fig. 4 shows a graphical illustration of the determined journey sequence plan
according to the first embodiment;
Fig. 5 shows, schematically, the construction of a second embodiment of the
destination call control with a central job manager as an interface between terminals and the individual lifts;
Fig. 6 shows, in a block-circuit diagram, the organisation of the jobs in a waiting
queue at a central job manager;
Fig. 7 shows an instantaneous state description of the lift A of the second
Fig. 8 shows an instantaneous state description of the lift B of the second
Fig. 9 shows the construction of an operator with a stop instruction, as used in the
Figure 1 shows schematically the construction of a destination call control 1 according to the invention with situation-induced journey sequence planning of the traffic volume of an individual lift. The destination call control is constructed as a multi-agent system. The basis of the multi-agent system is a capable communications network 2, by way of which
three devices, which are distributed in the building, for destination call input, so-termed terminals 3.1, 3.2, 3.3, are connected with a decentral job manager 4.
In ideal manner, an architecture for spontaneous networking is selected as the communications network 2. In this embodiment an ad-hoc network, which is known per se, with the designation IRON is provided. IRON assists spontaneous networking and is thus a decisive precondition for a configuration-free control.
Known examples for architectures for spontaneous networking are 'Jini', 'Universal Plug and Play' and 'Bluetooth'. In such a communications network 2 apparatus capable of networking, so-termed agents, log-on and interact without need for a configuration or an administration. The integration of all these apparatus and the services implemented thereat run fully automatically. The most important methods of such a communications network 2 are 'register', 'lookup' and 'notify'.
Through 'registration', the individual apparatus log-on in the network and make their services known.
Through 'lookup', one apparatus can find another apparatus or a required service. Through 'notification', one apparatus can log-on at another for information about the entry of specific events.
In a lift group, terminals, drives, cage doors, central job managers and/or decentral job managers log-on as apparatus capable of networking.
Terminals log-on in the network with their storey position and x,y-co-ordinates in
the network and inform themselves about all job managers present.
Drives represent the physical components of the lift control. They make
information available about which storey they can travel to, how many shaft doors
are located at a storey and at which side these are positioned. In addition,
information can be subscribed to at the drive with regard to specific events such as
change of the selector and change of the state (for example, travelling, arriving,
Cage doors log-on with information about the drive to which they belong, the deck
at which they are disposed and the side at which they open. By way of this
information the job manager immediately finds out how many decks a lift has and how many doors per deck are present.
Job managers log-on in the network with information about which drives they represent; a single one in the strictly decentral concept or all those present in the strictly central concept.
In principle any number of components can log-on in the network. The traditional group concept of lifts is thus superfluous and, in particular, any number of lifts with quite different layouts can be present in one group.
If, for example, eleven drives log-on, of which three have only one door, four each have three doors on two decks and four each have six doors uniformly distributed on three decks, then there is present an example of a so-termed heterogeneous multi-decker group consisting of
three single-deckers with only one door
four double-deckers, wherein one deck is equipped with one door and the other
decks with two doors
four triple-deckers, in which each deck has two doors.
The job manager of each individual lift is in a position of recognising, and correctly processing in the control, the number of decks and doors of its associated drive. This comprises in particular:
The planning system plans, in the case of a multi-decker, the boarding and alighting of the passengers by way of all decks which are present. The taxi driver of the job manager transmits at a stop the door opening commands to all doors which open at storeys at which passengers wish to board or alight.
In the case of the IRON communications network 2 used here, agents can mutually inform about changes and prepare and integrate data in the own operating logic. An agent can find out, via broadcast, which other agents have logged-on in the network and transmit communications to other agents. Moreover, an agent can subscribe to data at another agent.
The individual components of this multi-agent system - the so-termed agents - are, apart from the above-mentioned terminals, the job manager 4 which integrates all components necessary for the logical and physical control of a lift. These are here a planning system or planner 5, a broker 6, a door manager 7, a taxi driver 8, the drive 9 of the lift and an observer 10.
The terminals 3.1, 3.2., 3.3 are equipped with intelligent booking software and directly ask each job manager 4 for a transport offer for the respectively registered destination call. The communication between terminals and job managers 4 is carried out by means of contract network protocols. Each of the terminals 3.1, 3.2, 3.3 is equipped with a device for identification of passengers, to which a configuration manager 11 belongs.
The actual building layout, such as, for example, the number of storeys, access zones, division of the passengers into passenger groups, access authorisations, service requirements, etc., and passenger data are stored in the configuration manager 11 to be capable of calling up. On registration of a destination call, each terminal can call up passenger data from the configuration manager 11 and pass the data on to the broker 6. Thus, each terminal can, for example, check whether the registered passenger has access permission for the desired destination storey. If the check is successful, then the terminal asks the job manager 4 of the lift for its transport offer.
The planner 5 itself plans the optimal serving of the new passenger with consideration of the actual, lift-specific traffic situation and in that case produces an optimal plan which is then passed on to the broker 6, which is described further below, for control of the drive 9 of the lift. The starting point for the planner 5 is a situation representation which is actual at each point in time at which the broker 6 records new passengers, whereas the observer removes conveyed passengers.
The broker 6 communicates with the three terminals 3.1, 3.2, 3.3 by way of a two-stage contract network protocol. It receives the inputs of the terminals 3.1, 3.2, 3.3, records them in the situation representation of the planner 5, checks the generated optimal plan with respect to the effect of the newly included passenger on the transport of the already booked passengers and communicates the transport offer to the terminal. If no plan could be found because, for example, the problem cannot be solved due to insoluble conflicts between the passenger groups for this lift, then the broker 6 also informs the
corresponding terminal about that fact. If the passenger is booked then the broker 6 sends to the taxi driver 8 the actual journey sequence plan. The terminal now carries out the indication on the display.
The observer 10 monitors the state of the lift installation and updates the situation representation for the planner 5. If it thus establishes that the lift has stopped at a storey and the doors were correctly opened, then all passengers are flagged as -served- for whom -boarded- applies and the destination of whom corresponds with the storey. Passengers still waiting there are flagged as -boarded-, since they board when the lift has arrived at them. The observer 10 in that case has no knowledge of the plan or the activities of the taxi driver 8, but is supported solely on the information to which it has subscribed at the drive 9 and at the door manager 7. This is a precondition also for the occurrence of a special operation such as, for example, triggering of the control in the case of fire, which control takes over controlling by way of the drive 9 and interrupts the taxi driver normal operation in order to ensure that the situation representation is correctly updated in correspondence with the actually occurring changes in state.
The taxi driver goes over its respective actual plan, i.e. it transmits the corresponding commands to the drive 9 of the lift and the drives of the doors. It knows from its actual plan where the lift is to next stop in accordance with schedule and how long the doors have to be open so that all passengers have sufficient time for boarding and alighting. How many passengers change state at a stop was already determined by the planner 5. If the taxi driver 8 no longer has a plan, then it releases the lift so that this can be parked. In any situation the taxi driver 8 can exchange its actual travel plan for the actual plan sent thereto by the broker 6. How this change takes place depends on in which implementation state the taxi driver is disposed. Thus, for example, it is necessary that a stop process, once begun, of the old plan must firstly be concluded before the taxi driver 8 can travel to the first stop of the new plan.
The drive 9 executes the travel and stop commands which it obtains from the taxi driver 8 and, in addition, it learns the travel times of the lift between the individual storeys. It makes the travel timetable available to the planner 5 for the optimisation and also reports where the lift is actually disposed and in which direction it travels or whether it has just stopped.
The door manager 7 manages all doors of the lift and monitors whether the doors correctly open and close. In that case, doors can be present on different sides of the cage. It also determines the door opening and closing times of the doors and communicates them to the planner 5 for optimisation of the serving times of the passengers.
Each of the components is implemented as an independent agent which executes independent actions in the case of occurrence of specific events. In particular, the most diverse events can thereby be superimposed. Thus, for example, the broker can simultaneously receive the enquiries of different terminals 3.1, 3.2, 3.3 and submit them to the planner 5, The decentral job manager can make parallel delivery of an offer for several jobs whilst the booking of other jobs is still outstanding. The jobs are obligatory only when the corresponding terminal books.
Since between the delivery of the offer by the broker 6 and the booking by the respective terminal a time period of any length can in theory pass, it is possible that in the interim another terminal has already placed a booking. In this situation the broker 6 must check whether the delivered offer is still valid when the terminal now sends its booking. This random superimposition of enquiries and bookings makes it necessary for the terminal to wait for an acknowledgement of its booking and, in the case of absence of an acknowledgement, to seek an alternative booking at another job manager 4. If the replanning is also unsuccessful because the situation in the lift has, for example, changed in such a manner that irresolvable conflicts between the already booked passenger and the new passenger to be booked now arise, then the terminal receives a corresponding feedback.
Figure 2 shows a pool of requested and offered jobs Job 1 to Job 4 at a decentral job manager 4. Each terminal 1,2 usually has only one concrete job Job X or Job Y which it wishes to book at a lift. It accordingly sends this job to all job managers 4, which are known to it, of the group of lifts of which it knows from the drive data whether the associated lift can serve not only the boarding storey but also the alighting storey, of the passenger. Unnecessary requests to lifts which do not, in principle, come into question for the transport, are thus avoided.
Two kinds of jobs are present at the decentral job manager 4: these are, on the one hand, jobs, i.e. the Jobs X, which were requested and for which the job manager 4 has to
compute an offer, and on the other hand Jobs Y for which the job manager 4 has already delivered an offer, but does not yet know whether the terminal is actually booked with it.
In the case of the first embodiment illustrated here and shown in Figure 1 only a single lift is present. The lift can, however, also be part of a lift group. The invention is usable, without restriction, for such lift groups. In the case of a lift group, also, the terminals 3.1, 3.2, 3.3 directly ask the job managers 4 of the individual lifts for a transport offer. The terminals 3.1, 3.2, 3.3 independently collect these offers, compare them and compute the optimal booking of the passenger. Each lift subject of an enquiry computes independently of the others and with consideration of the actual lift-specific traffic situation its optimal journey sequence plan for serving the new passenger. The offer of each lift subject of an enquiry is sent back to the terminal, which selects the best offer and commissions the corresponding lift with the transport of the passenger. If the job manager 4 confirms the booking relative to the terminal from which the transport offer had been requested, then the booking is obligatory and is indicated to the passenger at the terminal. If a job manager no longer reports, then the terminal also reacts thereto and does not wait endlessly for the lacking offer.
The mode of operation of the destination call control according to the invention as described so far is, according to Figure 1, described in the following by way of the example of a planning problem of a lift installation with only a single lift with a single-door cage, which services a building (not illustrated here) with stopping points at seven storeys f1 to f7. The lift cage stands, at the moment, at storey f4. A passenger PI waits at storey f2 and wants to go to storey f7 and a further passenger P2 is already in the cage and wants to go from storey f1 to storey f5. The journey sequence of the cage is to be organised in accordance with the invention by means of planning system 3.
The characteristics of the lift, i.e. the instantaneous operational state of the lift, are detected and actualised in the situation representation by the observer 10. The characteristics of the passengers PI, P2 and particularly the destination calls of the passengers PI, P2 are passed on by way of terminals 3,1, 3.2, 3.3, in conjunction with the configuration manager 11, as input magnitudes of the destination call control 1 to the broker 6, which records them in the situation representation of the planner 5, as shown in Fig. 2.
Thus, in each planning process, which is started, for example, by registration of a destination call, the determined operational state and the desired objective state, thus the change in state of the lift to be achieved, are declaratively combined in a state description 14 comprehensible for the planning system 3, which is illustrated jn Figure 3.
The state description 14 depicted here in Figure 3 is expressed in the plan representational language PDDL according to McDermott et al., 1998. There are known to the expert also other modelling languages which differ with respect to their expressive power and which the expert can use for description of the situation representation without thereby changing the core of the invention. However, in selection of a planning system attention is to be given to the fact that this makes available planning algorithms of appropriate power for the modelling.
The reported passengers PI. P2 and the storeys f1 to f7 of the building are initially made known to the planning system 3 in an object declaration 15 in the state description 14 illustrated in Figure 3. A typified constant is imported for each object. For the lift 2 under consideration here, these are the waiting passenger PI, the passenger P2 already in the cage and all seven storeys f1 to f7.
(p1 - passenger)
(p2 - passenger)
(f1,f2,f3, f4,f5, f6, f7 - floor))
The broker 6 obtains details with respect to the topology of the building from the configuration manager 11. This is to be found as a topology description 16 in the state representation 14 again in the form of
(upper f1 f2) (upper f1 f3) (upper f1 f4)
(upper f 1 f5) (upper f1 f6) (upper f 1 f7)
(upper f2 f3) (upper f2 f4) (upper f2 f5)
(upper f2 f6) (upper f2 f7) (upper f3 f4)
(upper f3 f5) (upper f3 f6) (upper f3 f7)
(upper f4 f5) (upper f4 f6) (upper f4 f7)
(upper f5 f6) (upper f5 f7) (upper f6 f7)
In the topology description 16 the (upper ?fi, ?fi) prescriptions establish in each instance that the storey fj lies above the storey fi. The representation of the building topology is not absolutely necessary. In a simplification, the explicit topological description 16 of the building can be dispensed with in other embodiments of the method subject to the assumption that from each storey every other storey can be served by the lift.
The actual transport request 17 with the destination calls of the passengers P1 and P2 consisting of boarding storeys, i.e. 'origin', and destination storey, i.e. "destin', is represented as
(:init (origin p1 f2) (origin p2 f1) (destin p1 f7) (destin p2 f5) (boarded p2).
The transport request 17 additionally contains, from a journey sequence planned earlier, the information 'boarded p2', namely that passenger P2 has already boarded and is in the cage. This information was inserted into the state description by the observer 10.
Fundamentally, within the scope of the journey sequence planning each passenger PI, P2 occupies the three states: 'waiting', 'boarded' and 'served', which are defined as follows:
waiting: the passenger waits in front of the lift door. Here the lift is initially to stop at
the starting location, i.e. 'origin', of the passenger and only thereafter at the
destination storey, i.e. 'destin', indicated by the passenger.
boarded: the passenger is located in the lift cage and is transported to his or her
destination storey, i.e. 'destin', which has not been travelled to previously, i.e.
sen/ed: the passenger has left the lift cage at his or her destination storey, i.e.
'destin'. This transport request is concluded and the passenger was satisfactorily
served by the lift.
These three possible states can be expressed by means of the two commands -boarded ?p- and -served ?p- in the PDDL modelling language. The passenger P1 waits for a lift cage and accordingly is registered neither as -boarded- nor as -served-.
The observer 10 sets the actual position 18 of the lift cage, which is expressed in the state representation 14 as
The objective 19 for the planning system 5 is formulated in the state description 14 as:
(:goal (forall (?p - passenger) (served ?p)).
The shortest sequence of stops which transfers all passengers PI, P2 into the state of -served- is now sought, this being achieved precisely when the passengers have alighted at their destination storey -destin-.
Apart from the descriptions of the initial state and the objective state of the planning problem by the state description 14, there is transferred to the planning system 3 also an operator description 12. In the embodiment illustrated here, a stop operator as well as an operator for upward travel -up- and an operator for downward travel -down- are transferred for the modelling of the state transitions between initial state and objective state. As an alternative to these operators -stop-, -up- and -down-, the expert also knows other operators by which the desired change in the lift state can be achieved. In a given case and with appropriate definition of the parameters, the core of the invention is not thereby changed. In PDDL syntax according to McDermott et al., 1998, the following stop operator is here available:
(define (domain miconic) (:requirements :adl) (types passenger - object) floor - object)
(origin ?person - passenger ?floor - floor)
(destination ?person - passenger ?floor - floor) (boarded ?person - passenger) (served ?person - passenger)
(:action stop : parameters (?f - floor) : precondition (and (lift-at ?f))
: effect (and (forall (?p - passenger) (when (and (boarded ?p) (destination ?p ?f))
(and (not (boarded ?p)) (served ?p)))) (forail (?p - passenger) (when (and (origin ?p ?f) (not (served ?p))) (boarded ?p)))))
The operator for the upward travel is represented as:
(: action up
: parameters (?f1 - floor ?f2 - floor)
: precondition (and (lift-at ?f1) (upper ?f1 f2))
: effect (and (lift-at ?f2) (not (lift-at ?f1))))
The operator for the downward travel is expressed as:
(: action down
: parameters (?f1 - floor ?f2 - floor)
: precondition (and (lift-at ?f1) (upper ?f1 f2))
: effect (and (lift-at ?f2) (not (lift-at ?f1))))
The stop operator signals to the control of the drive 9 of the lift that the cage has to stop at a specific storey f1 to f7. The stop operator is so defined in the example of embodiment illustrated here that it includes the opening and closing of the doors. The opening and closing of the cage doors can, however, also be considered as a separate additional basic instruction to the door manager 7 of a lift 2 or the stop operator can be refined to the effect that a lift can also open and close the doors.
The operators for upward travel -up- and downward travel -down- give the instructions in terms of control technology to the drive control to set the drive 9 into operation in the appropriate direction. The taxi driver 8 presets the sequence in time in which the drive 9 is controlled by means of the operators.
A change in the passenger state is possible basically exclusively at a stop of the cage. Proceeding from rational behaviour of the passengers, in the case of a scheduled stop of the lift cage at a storey all passengers who wait at this storey -origin- in order to be transported in the cage get on board and all passengers leave the cage when this stops at their destination storey -destin-. The thereby occurring change is here registered in the stop operator with the help of the observer 10 and thereby taken into consideration in the journey sequence planning of the planning system 5. Like the operators -up- and -down-, the stop operator is then also effective as an instruction for the drive 9 if the criteria coded in -effect- are all fulfilled or entered. If. in the example described here, ?f = f5 is selected in the stop operator, then P2 disembarks in correspondence with the state description 14 and the behaviour model when -boarded p2- and -destin p2 f5- apply as described in the stop operator as -effect- of the operator instance stop(f5).
The data to that extent declared either in the operator description or as data of the state description 14 are passed on to the planning system 5 for computation of the optimal journey sequence plan.
Planning systems 5 are already known from other technical fields. In this example an IPP planning system 3, as appears from Koehler et al., 1997, 'Extending planning graphs to an ADL subset', in Steel, S, Proceedings of the 4th European Conference on Planning, pp. 273-285, Springer, Vol. 1348 of LNAI, available under http://www.informatik.uni-freiburg.de/'-koehler/ipp.html, searches for an applicable sequence of STOP instructions which fulfills the planning objective 13 (:goal(forall (?p - passenger) (served ?p)). Other planning systems can also be used insofar as these are in the position of generally detecting and processing the instantaneous situation representation.
In principle, the planning system 5 independently selects, in the case of input of the state description 14, instances on the basis of the operators made available by way of the operator description and also determines the sequence in the ascertained journey
sequence plan 20. The planning system 5 determines each time the parameters for the three operators -stop-, -up- and -down-, which produce a desired change in state.
The result thereof is, in this embodiment, a planned journey s.equence, i.e. the optimal plan, which is represented in graphical form in Fig. 3.
Time step 0: up f4 f5
Time step 1: stopfS
Time step 2: down f5 f2
Time step 3: stop f2
Time step 4: up f2 f7
Time step 5: stop f7
This computed optimal plan 13 is passed on to the broker 6. The broker 6 thereupon checks the generated optimal plan, how the newly planned-in passenger P1 has an effect on the transport of the already booked passenger, and communicates the transport offer to the terminal.
In the embodiment described here only a destination call is present for the planning. Consequently, an offer is to be delivered only for one job. Accordingly, no other jobs are booked by other terminals 3.1, 3.2, 3.3 between the offer computation by the decentral job manager 4 and the booking by the respective terminal. For this reason the acknowledgement of its booking at the terminal is redundant, but the booking is immediately obligatory. The terminal now undertakes the indication on the display and the broker transmits to the taxi driver 8 the actual optimal journey sequence plan 20.
The taxi driver 8 goes over this actual journey sequence plan 20, i.e. it transmits the corresponding command in the form of respective operators to the drive 9 of the lift and to the drive of the doors.
This journey sequence plan 20 has the effect that the lift cage in step 0 travels from the actual storey f4 at which it is disposed to the next stop at storey f5, -stop f5-. There the lift cage stops according to step 1 -stop f5- and the cage door opens at the predetermined time, so that the passenger P2 alights and is thus served, 'served'. In step 2, the lift cage travels downwards from f5 to f2 -down f5 f2- and stops in step 3 at storey f2 -stop f2-.
There passenger P1 boards. In step 4 the lift travels upwards from storey f2 to f7 -up f2 f7- and stops in the last step 5 at storey f7 -stop f7-. There also passenger P1 can now alight. Through this journey sequence 13 all passengers P1, P2 are transferred into the state -served- and the objective formulation 10 of the journey sequence plan is thus achieved.
Whilst the taxi driver 8 executes the optimal journey sequence plan 13, the observer 10 monitors the state of the lift installation and continuously updates the situation representation for the planner 5, In step 1 it thus establishes that the lift has stopped at the storey f5 and the doors were opened correctly; it flags the passenger P2 as -served-. In step 2 the observer 10 flags the passenger PI, who waits at the storey f2, as -boarded-. Subsequently, the lift cage stops at the storey f7 and, after the doors have been correctly opened, the observer 10 also sets the passenger PI in the situation description as 'served' and the actual position 9 of the lift cage in the state representation 5 at storey f7.
This generated journey sequence plan 20 does not, however, necessarily have to be fully executed, but if the state or the characteristics of passengers and/or the installation change in relevant manner before it is completely executed, according to the invention a next planning cycle is started and an optimal journey sequence plan 20 for the new planning situation is created. No plan modification therefore takes place.
Figure 5 shows schematically the structure and basic build-up of a second embodiment of the destination call control according to the invention. The destination call control 25 comprises a central job manager 26 and two decentral job managers, a configuration manager 29 as well as a terminal 30 representative of all terminals present, these components being interconnected by way of a communications device 31. The build-up and function of the decentral job managers 27, 28 substantially correspond with those of the decentral job manager 4 of the first embodiment.
The destination call control is here organised as a so-termed group control of the traffic of a lift group with two lifts A and B in a building with stopping points at seven storeys. The planning task in that case is represented as follows:
The lift cage A travels, at that moment, upwardly; it is disposed at that instant at storey f2 and can still reach the storey f3. The lift cage B stands at that instant at the storey f1. Lift
The service requirements are known in each case within the scope of the passenger recognition from the configuration manager 29 and passed on from the central job manager 26 as part of a job, or an offer enquiry, to the decentral job managers 27, 28 of the individual lifts A, B. Specific service requirements for all or any selected passengers can be provided to be activatable in dependence on the state of the lift installation or ihe building or even in dependence on the time of day. In addition, through the use of a planning system for the journey sequence determination there can be represented a flexible weighting of the individual service requirements, especially the VIP requirement, in dependence on traffic volume.
Here the following service requirements are provided:
Division of all passengers into two groups 'conflict_A' and 'conflict_B', who may
never go into the lift;
Passengers of the type 'never_alone', for whom a companion in the form of a
passenger of the type 'attendant' must be present in the lift during the journey. In
that case it is not absolutely necessary that always the same companion travels in
the lift during the journey, but this can also change;
Passengers of the type 'going_direct', who are conveyed to their destination
without an intermediate stop;
Passengers of the type 'vip', who are conveyed as a matter of priority before all
Passengers for whom an access restriction to specific storeys is formulated;
Passengers of the type 'going_up', who are transported exclusively upwards;
Passengers of the type 'going_down', which are transported exclusively
A passenger P1, P2 can thus quite readily be the subject of a number of service requirements; however, these should not conflict, so that the passenger can also be efficiently conveyed. Two passengers P1, P2, for example, are an elemental conflict, for which the following typification is declared:
(P1 (either conflict_A never_alone)) (P2 (either conflict_B attendant))
P1 here may not travel solely in the lift and belongs at the same time to the passenger group A. The single possible companion P2 known to the system belongs, however, to the passenger group B; the passenger group A may never go into the lift. An accompanying thus infringes the exclusion condition and P1 can only be conveyed when another companion, who does not belong to the group B, becomes known to the system.
For lift A the object declaration 33 contains the already travelling passenger P1, i.e. a normal passenger, the new passenger P2, i.e. a VIP, and all seven storeys f1 to f7.
(p1 - passenger)
(p2 - vip)
(f1,f2,f3, f4,f5, f6. f7 - floor))
In this embodiment an express description of the building topology is dispensed with on the assumption that from each storey each other storey can be served.
The actually registered transport request 34 of the passengers P1 and P2 is represented as
(:init (origin pi f1) (origin p2 f3) (destin p1 f7) (destin p2 f7) (boarded p1)
Fundamental to the transport request 34 is the standard assumption that passengers wait at the storey when no corresponding 'boarded' information is present. Precisely, this signifies here that passenger P2 waits at the storey. The access restriction for passenger P1 is represented therein as
(no-access p1 f3) (no-access p1 f4)
The actual position 35 of the lift cage 2 of the lift A is expressed as
in the state description 32. Alt expressed facts are weighted as true and all others as false.
The objective 36 for the planning system is formulated as
(:goal (forall (?p - passenger) (served ?p)).
The shortest sequence of stops which transfers all passengers P1, P2 into the state of 'served' is sought, which is achieved precisely when they have disembarked at their destination storey or storey f7.
Since in this embodiment only a minimal stop sequence is to be determined, the planning system also receives only one so-termed stop operator 37, from which the system can construct a valid journey sequence plan. In Fig. 9 there is illustrated an example of a stop operator 32. The modelling language PDDL according to McDermott et al., 1998, here too serves for pictorialisation as before in the state description 32. The stop operator 37 contains a prescriptive description 38 in which it is described when a stop of a lift A, B at a storey f 1 to f7 is permissible. Here the access restriction -no-access- which in that case is defined concretely either for a passenger or, however, for a passenger group, and a function instruction 39 in which it is established at which storey f1 to f7 a lift cage shall stop at a permissible stop and what effect this stop has on the actual state of the lift installation 18. Preconditions of the function instruction 39 in that case represent the user-specific conversion of the desired service requirements. The complex stop operator shown in Figure 9 makes it possible to bypass the planning system 21 by all service requirements imported into the passenger and object declaration 33.
For the planning example described here, only the preconditions, which are underlined in Fig. 5, of the operator 32 are relevant, which preconditions formulate the conditions at a stop at a storey f1 to f7 in the presence of VIPs and passengers with access restriction.
The instantaneous situation representation 32 created to that extent for each lift A is passed on to the planning system belonging to the lift A.
The suitable planning systems used in accordance with the invention operate independently of the actual planning problem. Such planning systems are already known from other technical fields.
In this second embodiment, too, an IPP planning system, as known from Koehler et al., 1997, Extending planning graphs to an ADL subset, appearing in Steel, Proceedings of the 4th European Conference on Planning, pp. 273-285, Springer, Vol. 1348 of LNAI, and available under http://www.informatik.uni-freiburg.de/-koehler/ipp.html. seeks a valid sequence of STOP instructions which fulfill the planning objective 31. Other planning systems can also be used insofar as these are in a position of detecting and processing the instantaneous situation representation in its entirety.
In solving a concrete planning task, the planning system selects the operators, which are to be used in the journey sequence plan, of the operator description 23, here the stop operator 37. If service requirements, such as, for example, 'VIP', 'going_direct', etc, occur in the state description 32, then the planning system independently checks the corresponding preconditions of the function instruction 39 of the operator 37. If a service requirement contained in the operator 37 as a precondition is absent in the call-relevant state description 32, then this is automatically disregarded as a superfluous precondition of the operator 37. An example of a service requirement not taken into consideration here is the precondition -attendant-. Concrete values for operator parameters as well as an arrangement sequence in which operators occur in the journey sequence plan are then determined. This arrangement sequence specifies the execution sequence of the operators in the journey sequence and thus the journey sequence for serving the respective destination call.
The planning system cannot find a solution for lift A: passenger P2 shall be immediately conveyed, i.e. the lift A has to stop at f3. However, P1 is in the lift and has no access to f3. A stop at f3 is thus possible only after PI has disembarked, i.e. the lift A must first travel to storey f7; this in turn is not allowed, since the VIP condition requires VIPs to be conveyed ahead of all other passengers.
The situation 42 can be solved by the planning system for the lift B (Figure 8) without problems, since lift B does not know the passenger PI at all, because he or she is in fact underlay in the lift A and only the new passenger P2 is reported. The object declaration
43 for lift B at the planning system consequently contains also only the new passenger P2, who is typified by the service requirement VIP, and all seven storeys f1 to f7.
(p2 - vip)
(f1,f2, f3, f4, f5, f6, f7 - floor))
Moreover, from each storey each other storey can be served.
The actual transport request 44 of the passenger P2 is represented as
(origin p2 f3) (destin p2 f7).
The actual position description 45 of the lift cage B is expressed in the state description 42 as
In the case of the lift B, the objective formulation 46 for the planning system is identical with that of the lift A. It is transferred to the planning system together with the object declaration 43 and the above-described stop operator 37 as part of the situation representation 42 of the lift B. For planning of the journey sequence of the lift B, only the operator precondition 'stop at a storey in the presence of VIP' is relevant, because the state description 32 for lift B also transfers to the planning system only the service requirement VIP. All remaining service requirements provided in the form of prescriptions 33 and preconditions of the function instruction 39 of the STOP operator 37 remain unconsidered in this planning sequence and accordingly without effect on the journey sequence plan 24.
The planning system 21 generates, starting from this input, the following journey sequence plan for lift B:
time step 1: (stop 3)
time step 2: (stop 7),
which represents a minimum stop sequence for successful conveying of the passenger P2.
If the results of the journey sequence plan of the lifts A, B are entered at the central job manager 26, this then weights the two journey sequence offers of the lifts A, B. The li^ with the best offer is selected by the central job manager 26. The best solution is here the single possible journey sequence plan of the lift B. Consequently the central job manager books the passenger P2 on the lift B. Lift B also actualises the journey sequence plan after receipt of the booking; all other lifts carry on travelling in accordance with their previous plan.
1. Method for journey sequence planning of a lift installation, in which a journey sequence optimal with respect to a predeterminable optimisation criterion is determined for journey enquiries detected by way of a sensor system, characterised in that a situation-based search process for determining the optimal journey sequence is provided and determines an actual journey sequence in the case of each relevant change in a planning situation.
2. Method according to claim 1, characterised in that in the case of each relevant change in a planning situation, detected actual data specific to persons and the installation and relevant to planning are combined into a form, which is understandable by the search process, in a situation representation.
3. Method according to claim 1 or claim 2, characterised in that the actual operational state of the lift installation, the objective state to be produced of the lift installation and one or more operators specifying elemental state transitions of the lift installation are supplied in the situation representation to the search process.
4. Method according to claim 3, characterised in that detected data specific to persons and the installation and relevant to planning are combined into a form, which is understandable by the search process, in a situation representation, wherein the operators are constructed in modular form and contain instructions, which relate to control technology, with respect to service requirements.
5. Method according to claim 4, characterised in that in the case of a lift group several service requirements are served simultaneously by several lifts of the lift group.
6. Destination call control for determination of the journey sequence of one or more lift cages of a lift installation, comprising at least one call registration device for detecting journey requests and a processing unit for determining a journey sequence, which is optimal with respect to a given optimisation criterion, for registered journey requests, characterised in that a planning system is provided as processing unit and determines the situation-specific optimal journey sequence.
7. Destination call control according to claim 6, characterised in that the planning system is part of a multi-agent system, wherein the call registration device is operatively connected with the planning system by way of a communications network.
8. Lift installation consisting of at least one lift with one deck and at least one lift with two decks and a destination call control according to claim 6.
9. Method for journey sequence planning of a lift installation substantially
as herein described with reference to the accompanying drawings.
10. Destination call control for determination of the journey sequence of one
or more lift cages of a lift installation substantially as herein described
with reference to the accompanymg drawings.
|Indian Patent Application Number||IN/PCT/2002/1480/CHE|
|PG Journal Number||52/2007|
|Date of Filing||18-Sep-2002|
|Name of Patentee||INVENTIO AG|
|Applicant Address||Seestrasse 55, CH-6052 Hergiswil,|
|PCT International Classification Number||B66B 1/18|
|PCT International Application Number||PCT/CH2001/000205|
|PCT International Filing date||2001-03-29|