Interval scripts: a programming paradigm for interactive environments and agents

ABSTRACT

 In this paper we present interval scripts, a new paradigm for the programming of interactive environments and computer characters. In this paradigm, actions and states of the users and the system computational agents are associated with temporal intervals. Programming is accomplished by establishing temporal relationships as constraints between the intervals. Unlike previous temporal constraint-based programming languages, we employ a strong temporal algebra based in Allen's interval algebra with the ability to express mutually exclusive intervals and to define complex temporal structures. To avoid the typical computational complexity of strong temporal algebras we propose a method, PNF propagation, that projects the network implicit in the program into a simpler, 3-valued (past, now, future) network where constraint propagation can be conservatively approximated in linear time. The interval scripts paradigm is the basis of ISL, or Interval Scripts Language, that was used to build three large-scale, computer-vision-based interactive installations with complex interactive dramatic structures. The success in implementing these projects provides evidence that the interval scripts paradigm is a powerful and expressive programming method for interactive environments.

REFERENCES

• 1: Randy Pausch , Jon Snoddy , Robert Taylor , Scott Watson , Eric Haseltine, Disney's Aladdin: first steps toward storytelling in virtual reality, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.193-203, August 1996 [doi>10.1145/237170.237257]
• 2: Aaron F. Bobick , Stephen S. Intille , James W. Davis , Freedom Baird , Claudio S. Pinhanez , Lee W. Campbell , Yuri A. Ivanov , Arjan Schütte , Andrew Wilson, The KidsRoom: A Perceptually-Based Interactive and Immersive Story Environment, Presence: Teleoperators and Virtual Environments, v.8 n.4, p.369-393, August 1999 [doi>10.1162/105474699566297]
• 3: 3. Tosa N. Expression of emotion, unconsciouness with art and technology. In: Hatano G, Okada N, Tanabe H (eds) Affective minds, Elsevier, 2000, pp 183-205.
• 4: C. S. Pinhanez , J. W. Davis , S. Intille , M. P. Johnson , A. D. Wilson , A. F. Bobick , B. Blumberg, Physically interactive story environments, IBM Systems Journal, v.39 n.3-4, p.438-455, July 2000
• 5: Jennifer Lai , Anthony Levas , Paul Chou , Claudio Pinhanez , Marisa Viveros, BlueSpace: personalizing workspace through awareness and adaptability, International Journal of Human-Computer Studies, v.57 n.5, p.415-428, November 2002 [doi>10.1006/ijhc.1028]
• 6: James L. Crowley , Joëlle Coutaz , François Bérard, Perceptual user interfaces: things that see, Communications of the ACM, v.43 n.3, p.54-ff., March 2000 [doi>10.1145/330534.330540]
• 7: Ramesh Raskar , Greg Welch , Matt Cutts , Adam Lake , Lev Stesin , Henry Fuchs, The office of the future: a unified approach to image-based modeling and spatially immersive displays, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.179-188, July 1998 [doi>10.1145/280814.280861]
• 8: G. D. Abowd, Classroom 2000: an experiment with the instrumentation of a living educational environment, IBM Systems Journal, v.38 n.4, p.508-530, Dec. 1999
• 9: Elizabeth D. Mynatt , Irfan Essa , Wendy Rogers, Increasing the opportunities for aging in place, Proceedings on the 2000 conference on Universal Usability, p.65-71, November 16-17, 2000, Arlington, Virginia, United States [doi>10.1145/355460.355475]
• 10: 10. Pentland A. Smart rooms. Scientific American 1996; 274(4): 68-76.
• 11: Chris Shaw , Mark Green , Jiandong Liang , Yunqi Sun, Decoupled simulation in virtual reality with the MR toolkit, ACM Transactions on Information Systems (TOIS), v.11 n.3, p.287-317, July 1993 [doi>10.1145/159161.173948]
• 12: 12. Pausch R, Burnette T, Capeheart AC, et al. A brief architectural overview of Alice, a rapid prototyping system for virtual reality. IEEE Computer Graphics and Applications 1995.
• 13: Claudio Santos Pinhanez , Aaron F. Bobick, Representation and recognition of action in interactive spaces, Massachusetts Institute of Technology, 1999
• 14: Claudio S. Pinhanez , Aaron F. Bobick, "It/I": a theater play featuring an autonomous computer character, Presence: Teleoperators and Virtual Environments, v.11 n.5, p.536-548, October 2002 [doi>10.1162/105474602320935865]
• 15: James F. Allen, Maintaining knowledge about temporal intervals, Communications of the ACM, v.26 n.11, p.832-843, Nov. 1983 [doi>10.1145/182.358434]
• 16: 16. Vilain M, Kautz H. Constraint propagation algorithms for temporal reasoning. In: Proceedings of AAAI'86, Philadelphia, PA, 1986, pp 377-382.
• 17: Claudio S. Pinhanez , Kenji Mase , Aaron Bobick, Interval scripts: a design paradigm for story-based interactive systems, Proceedings of the SIGCHI conference on Human factors in computing systems, p.287-294, March 22-27, 1997, Atlanta, Georgia, United States [doi>10.1145/258549.258758]
• 18: 18. Coen MH. Building brains for rooms: designing distributed software agents. In: Proceedings of IAAI'97, Providence, CT, 1997, pp 971-977.
• 19: 19. Director's User Manual, MacroMind Inc. 1990.
• 20: 20. MAX Getting Started Manual, Opcode, 2002.
• 21: Curtis Roads, The Computer Music Tutorial, MIT Press, Cambridge, MA, 1996
• 22: Robert Rowe, Interactive music systems: machine listening and composing, MIT Press, Cambridge, MA, 1992
• 23: Andrew Rollings , Dave Morris, Game Architecture and Design, Paraglyph Press, 1999
• 24: M. Cecelia Buchanan , Polle T. Zellweger, Automatic temporal layout mechanisms, Proceedings of the first ACM international conference on Multimedia, p.341-350, August 02-06, 1993, Anaheim, California, United States [doi>10.1145/166266.168415]
• 25: Rei Hamakawa , Jun Rekimoto, Object composition and playback models for handling multimedia data, Proceedings of the first ACM international conference on Multimedia, p.273-281, August 02-06, 1993, Anaheim, California, United States [doi>10.1145/166266.168399]
• 26: Guido van Rossum , Jack Jansen , K. Sjoerd Mullender , Dick C. A. Bulterman, CMIFed: a presentation environment for portable hypermedia documents, Proceedings of the first ACM international conference on Multimedia, p.183-188, August 02-06, 1993, Anaheim, California, United States [doi>10.1145/166266.166287]
• 27: Michalis Vazirgiannis , Ioannis Kostalas , Timos Sellis, Specifying and Authoring Multimedia Scenarios, IEEE MultiMedia, v.6 n.3, p.24-37, July 1999 [doi>10.1109/93.790609]
• 28: Brian Bailey , Joseph A. Konstan , Robert Cooley , Moses Dejong, Nsync—a toolkit for building interactive multimedia presentations, Proceedings of the sixth ACM international conference on Multimedia, p.257-266, September 13-16, 1998, Bristol, United Kingdom [doi>10.1145/290747.290779]
• 29: Muriel Jourdan , Nabil Layaïda , Cécile Roisin , Loay Sabry-Ismaïl , Laurent Tardif, Madeus, and authoring environment for interactive multimedia documents, Proceedings of the sixth ACM international conference on Multimedia, p.267-272, September 13-16, 1998, Bristol, United Kingdom [doi>10.1145/290747.290780]
• 30: K. Selçuk Candan , B. Prabhakaran , V. S. Subrahmanian, CHIMP: a framework for supporting distributed multimedia document authoring and presentation, Proceedings of the fourth ACM international conference on Multimedia, p.329-340, November 18-22, 1996, Boston, Massachusetts, United States [doi>10.1145/244130.244234]
• 31: Stefan Agamanolis , V. Michael Bove, Jr., Multilevel Scripting for Responsive Multimedia, IEEE MultiMedia, v.4 n.4, p.40-50, October 1997 [doi>10.1109/93.641878]
• 32: Stefan Wirag, Modeling of Adaptive Multimedia Documents, Proceedings of the 4th International Workshop on Interactive Distributed Multimedia Systems and Telecommunication Services, p.420-429, September 10-12, 1997
• 33: 33. André E, Rist T. Coping with temporal constraints in multi-media presentation planning. In: Proceedings of AAAI'96, Portland, OR, 1996, pp 142-147.
• 34: 34. Kautz HA, Ladkin PB. Integrating metric and qualitative temporal reasoning. In: Proceedings of AAAI'91, Anaheim, CA, 1991, pp. 241-246.
• 35: 35. Krueger MW. Artificial reality II. Addison-Wesley 1990.
• 36: Benjamin B. Bederson , Allison Druin, Computer-augmented environments: new places to learn, work, and play, Advances in human-computer interaction (vol. 5), Ablex Publishing Corp., Norwood, NJ, 1995
• 37: 37. Dey AK, Salber D, Abowd GD. A conceptual framework and a toolkit for supporting the rapid prototyping of context-aware applications. Human-Computer Interaction Journal 2001; 16(1).
• 38: C. S. Pinhanez , A. F. Bobick, Human Action Detection Using PNF Propagation of Temporal Constraints, Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, p.898, June 23-25, 1998
• 39: 39. Meiri I. Combining qualitative and quantitative constraints in temporal reasoning. In: Proceedings of AAAI'91, Anaheim, CA, 1991, pp 260-267.
• 40: 40. Pinhanez CS, Bobick AF. PNF propagation and the detection of actions described by temporal intervals. In: Proceedings of DARPA image understanding workshop, New Orleans, LA, 1997, pp 227-233.
• 41: Rina Dechter, From local to global consistency, Artificial Intelligence, v.55 n.1, p.87-107, May 1992 [doi>10.1016/0004-3702(92)90043-W]
• 42: 42. Mackworth AK. Consistency in networks of relations. Artificial Intelligence 1977; 8(1): 99-118.
• 43: 43. Pinhanez CS. Computer theater. In: Proceedings of eighth international symposium on electronic arts (ISEA'97), Chicago, IL, 1997.
• 44: Christopher Richard Wren , Ali Azarbayejani , Trevor Darrell , Alex Paul Pentland, Pfinder: Real-Time Tracking of the Human Body, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.7, p.780-785, July 1997 [doi>10.1109/34.598236]
• 45: P. Maes , T. Darrell , B. Blumberg , A. Pentland, The ALIVE system: full-body interaction with autonomous agents, Proceedings of the Computer Animation, p.11, April 19-21, 1995
• 46: 46. Loyall AB, Bates J. Hap: A reactive, adaptive architecture for agents. Carnegie Mellon University, Technical Report CMUCS-91-147, Pittsburgh, PA, 1991.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Interaction styles (e.g., commands, menus, forms, direct manipulation)

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.0 General
  D.2 SOFTWARE ENGINEERING
      D.2.6 Programming Environments

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Temporal logic

General Terms:
Human Factors, Theory

Keywords:
Interactive spaces, Programming paradigms, Programming with constraints, System architecture, Temporal reasoning, Ubiquitous computing