Method and apparatus for controlling program sources in an interactive television system using hierarchies of finite state machines

• US 5,504,896 A
• Filed: 12/29/1993
• Issued: 04/02/1996
• Est. Priority Date: 12/29/1993
• Status: Expired due to Fees

• Current Assignee: AT&T IPM Corp. (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Schell, William M., Story, Guy A.
• Primary Examiner(s): Kriess, Kevin A.
• Application Number:
  US08/175,059
• Time in Patent Office: 825 Days
• Field of Search: 395/650, 395/700, 364/141
• US Class Current: 725/131
• CPC Class Codes: H04N 7/17336 Handling of requests in head-ends

Abstract

A method of using finite state machines (FSMs) is disclosed for controlling multiple processes in response to input signals. In an exemplary embodiment, such processes comprise facilities for providing interactive television services and multimedia signals for such services. The FSMs are arranged in a tree-like structure and communicate with each other by event messages of various types. Each FSM has multiple states and permitted state transitions. Transitions occur in response to event messages and/or input signals, and a transition can cause one or more event messages associated with such transition to be sent. At least one terminal FSM is associated with each of the multiple processes and controls that process. Status changes in each process can also cause state transitions in the FSMs. The FSMs are resident in the various processors controlling the multiple processes, which can be situated at different locations.

Claims

1. A method of controlling processes in an interactive system in response to input messages from users of said interactive system wherein a hierarchy of finite state machines (FSMs) is associated with each user, each FSM having multiple states and multiple permitted state transitions, each hierarchy having one or more first terminal FSMs for responding to said input messages from said user, one or more second terminal FSMs for providing control signals to said processes, and one or more director FSMs, said first terminal FSMs and said second terminal FSMs each being associated with a single director FSM at the next higher level in said hierarchy, each director FSM being associated with one or more first terminal FSMs, second terminal FSMs and/or director FSMs at the next lower level in said hierarchy and no more than one director FSM at the next higher level in said hierarchy, which comprises the steps of:

in each hierarchy;

causing selected state transitions to occur in said first terminal FSMs in response to selected input messages from the particular user associated with said hierarchy;

generating selected event messages for the director FSM associated with each first terminal FSM in response to selected state transitions in said first terminal FSM;

generating selected event messages for the first terminal FSMs, second terminal FSMs and/or other director FSMs associated with a particular director FSM in response to selected state transitions in said particular director FSM;

causing selected state transitions to occur in said first terminal FSMs, said second terminal FSMs and said director FSMs in response to selected event messages therefor; and

generating selected control signals for each process being used by said particular user in response to the occurrence of selected state transitions in said second terminal FSMs associated with said process;

the particular operation of said processes in response to said input messages being determined by the arrangement in said hierarchy of said first terminal FSMs, said second terminal FSMs and said director FSMs, the particular states and state transitions permitted for said first terminal FSMs, said second terminal FSMs and said director FSMs, the particular input messages and/or event messages causing each permitted state transition to occur and the particular event messages and/or control signals generated in response to the occurrence of each permitted state transition.

2. The method of claim 1 in which said first terminal FSMs, said second terminal FSMs and said director FSMs in each hierarchy are implemented in one or more processors by one or more computer programs.

3. The method of claim 2 in which each first terminal FSM, second terminal FSM and director FSM in each hierarchy is implemented in one of said processors and said processors are situated at one or more locations.

4. The method of claim 1 wherein at least one of said processes generates at least one status signal for at least one of said second terminal FSMs associated with said at least one process, which further comprises the steps of:

causing at least one of said state transitions in said at least one second terminal FSM to occur in response to said at least one status signal;

generating selected event messages for the director FSM associated with said at least one second terminal FSM in response to selected state transitions in said at least one second terminal FSM;

whereby the operation of said at least one process in response to said input messages is also determined by the particular status signals causing said state transitions to occur in said at least one second terminal FSM.

5. The method of claim 1 wherein at least one first terminal FSM, second terminal FSM or director FSM in each of at least two of said hierarchies generates at least one event message for a first terminal FSM, second terminal FSM or director FSM in another one of said at least two hierarchies, thereby permitting interaction among the users associated with each of said at least two hierarchies.

6. The method of claim 1 wherein said interactive system is an interactive television system and said processes are television program sources.

7. Apparatus for controlling processes in an interactive system in response to input messages from users of said interactive system, which comprises:

a hierarchy of finite state machines (FSMs) for each user, each FSM having multiple permitted states and multiple permitted state transitions, each hierarchy having one or more first terminal FSMs for responding to said input messages from said user, one or more second terminal FSMs for providing control signals to said processes and one or more director FSMs, said first terminal FSMs and said second terminal FSMs each being associated with a single director FSM at the next higher level in said hierarchy, each director FSM being associated with one or more first terminal FSMs, second terminal FSMs and/or director FSMs at the next lower level in said hierarchy and no more than one director FSM at the next higher level in said hierarchy;

means for causing selected state transitions to occur in said first terminal FSMs in each hierarchy in response to input messages from the user associated with said hierarchy;

means for generating selected event messages for the director FSM associated with each first terminal FSM in response to selected state transitions in said first terminal FSM;

means for generating selected event messages for the first terminal FSMs, second terminal FSMs and/or other director FSMs associated with a particular director FSM in response to selected state transitions in said particular director FSM;

means for causing selected state transitions to occur in said first terminal FSMs, said second terminal FSMs and/or said director FSMs in response to said event messages therefor; and

means for generating selected control signals for the processes being used by the user associated with each hierarchy in response to the occurrence of selected state transitions in said second terminal FSMs in said hierarchy;

the particular operation of said processes in response to said input messages for a given user being determined by the arrangement of the first terminal FSMs, second terminal FSMs and director FSMs in the hierarchy associated with said given user, the particular states and state transitions permitted for said first terminal FSMs, said second terminal FSMs and said director FSMs, the particular input messages and/or event messages causing each permitted state transition to occur and the particular event messages and/or control signals generated in response to the occurrence of each permitted state transition.

8. The apparatus of claim 7 wherein at least one of said processes generates at least one status signal for at least one of said second terminal FSMs in the hierarchy controlling said at least one process, which further comprises:

means for causing at least one of said state transitions in said at least one second terminal FSM to occur in response to said at least one status signal;

means for generating selected event messages for the director FSM associated with said at least one second terminal FSM in response to selected state transitions in said at least one second terminal FSM;

whereby the operation of said at least one process in response to said input messages is also determined by the particular status signals causing said state transitions to occur in said at least one second terminal FSM.

9. The apparatus of claim 7 wherein said interactive system is an interactive television system and said processes are television program sources.