More Web Proxy on the site http://driver.im/

research-article

Specification and Analysis of Real-Time Problem Solvers

Authors:

S. ShekharAuthors Info & Claims

IEEE Transactions on Software Engineering, Volume 19, Issue 8

Pages 788 - 803

https://doi.org/10.1109/32.238582

Published: 01 August 1993 Publication History

Abstract

The authors provide a method for the specification of real-time artificial intelligence (AI) problem solvers. Using this method, a formal specification of a real-time problem is presented. In addition, a method for analyzing real-time AI problem solvers is examined using a case study of two real-time problem solvers, namely DYNORAII and RTA* for the real-time path planning problem. New results on worst-case and average-case complexity of the problem, and of the algorithms that solve it, and an experimental evaluation of DYNORAII and RTA* for deadline compliance and response-time minimization are provided.

References

[1]

{1} R. E. Korf, "Real-time heuristic search first results," in Proc. AAAI Conf., 1987.

[2]

{2} N. J. Nilsson, Principles of Artificial Intelligence. Palo Alto, CA: Tioga Press, 1980.

[3]

{3} P. H. Winston, Artificial Intelligence. Reading, MA: Addison Wesley, 1984.

[4]

{4} C. L. Liu and J. W. Layland, "Scheduling algorithms for multiprogramming in a hard real-time environment," J. Assoc. Comput. Mach., pp. 46-61, Feb. 1973.

Digital Library

[5]

{5} M. R. Garey and D. S. Johnson, "Complexity results for multiprocessor scheduling under resource constraints," SIAM J. Computing, pp. 397-411, 1975.

Digital Library

[6]

{6} E. A. Lee and D. G. Messerschmitt, "Static scheduling of synchronous data flow programs for digital signal processing," IEEE Trans. Comput., vol. C-36, pp. 24-35, Jan. 1987.

[7]

{7} J. A. Bannister and K. S. Trivedi, "Task allocation in fault-tolerant distributed systems," Acta Informatica, pp. 261-281, 1983.

Digital Library

[8]

{8} C. M. Krishna and K. G. Shin, "On scheduling tasks with a quick recovery from failure," IEEE Trans. Comput., vol. C-35, pp. 448-455, May 1986.

[9]

{9} J. F. Kurose, M. Schwartz, and Y. Yemini, "Multiple-access protocols and time-constrained communication," Computing Survey, pp. 43-70, Mar. 1984.

Digital Library

[10]

{10} W. Zhao and K. Ramamritham, "Virtual time CSMA protocols for hard real-time communication," IEEE Trans. Software Eng., vol. SE-13, pp. 938-952, Aug. 1987.

Digital Library

[11]

{11} I. Lee and S. B. Davidson, "Adding time to synchronous process communication," IEEE Trans. Comput., vol. C-36, pp. 941-948, Aug. 1987.

[12]

{12} B. Dasarathy, "Timing constraints of real-time systems: Constructs for expressing them, methods of validating them," IEEE Trans. Software Eng., vol. SE-11, pp. 80-86, Jan. 1985.

Digital Library

[13]

{13} V. H. Hasse, "Real-time behavior of programs," IEEE Trans. Software Eng., vol. SE-7, pp. 494-501, Sept. 1981.

Digital Library

[14]

{14} D. W. Leinbaugh and M. R. Yamini, "Guaranteed response times in a distributed hard real-time environment," IEEE Trans. Software Eng., vol. SE-12, pp. 1139-1144, Dec. 1986.

Digital Library

[15]

{15} F. Jahanian and A. K. Mok, "Safety analysis of timing properties in real-time systems," IEEE Trans. Software Eng., vol. SE-12, pp. 890-904, Sept. 1986.

Digital Library

[16]

{16} J. E. Coolahan and N. Roussopoulos, "Timing requirements for time-driven systems using augmented petri nets," IEEE Trans. Software Eng., vol. SE-9, pp. 603-616, Sept. 1983.

Digital Library

[17]

{17} N. G. Leveson and J. L. Stolzy, "Safety analysis using petri nets," IEEE Trans. Software Eng., vol. SE-13, pp. 386-397, Mar. 1987.

Digital Library

[18]

{18} M. R. Garey and D. S. Johnson, Computers and Intractability. New York: W. H. Freeman, 1979.

[19]

{19} S. Shekhar and S. Dutta, "Minimizing response times in real time planning and search," in Proc. 11th Int. Joint Conf. Artificial Intelligence, 1989, pp. 238-242.

Digital Library

[20]

{20} L. P. Kaelbling, "An architecture for intelligent reactive system," in Reasoning about Actions and Plans: Proc. 1986 Workshop. Los Altos, CA: Morgan Kauffman, 1987, pp. 395-410.

[21]

{21} R. Reiter, "Nonmonotonic reasoning," in In Exploring Artificial Intelligence , H. E. Shrobe and AAAI, Eds. Los Altos, CA: Morgan Kauffman, 1988.

[22]

{22} R. E. Korf, "Search: A survey of recent results," in Exploring Artificial Intelligence, H. Shrobe, Ed. Los Altos, CA: Morgan Kauffman, 1988.

[23]

{23} P. E. Hart, N. J. Nilsson, and B. Raphael, "A formal basis for the heuristic determination of minimum cost paths," IEEE Trans. Syst. Sci. Cybern., vol. SSC-4, no. 2, pp. 100-107, 1968.

[24]

{24} R. E. Korf, "Depth-first iterative deepening: An optimal admissible tree search," Artificial Intelligence, vol. 27, pp. 97-109, 1985.

Digital Library

[25]

{25} K. Ramamritham, "Channel characteristics in local area hard real-time systems," Computer Networks and ISDN Syst., pp. 3-13, 1987.

Digital Library

[26]

{26} T. Dean and M. Boddy, "An analysis of time dependent planning," Proc. AAAI, pp. 49-54, 1988.

[27]

{27} S. Russel and E. H. Wefald, "Decision theoretic control of reasoning: General theory and an algorithm tO game playing," Report No. UCB/CSD 88/435, p. Computer Science Division, U.C. Berkely (1988).

[28]

{28} E.J. Horvitz, G. F. Cooper, and D. E. Heckerman, "Reflection and action under scarce resources: Theoretical principles and empirical study," in Proc. 11th Int. Joint Conf. Artificial Intelligence, IJCAI, 1989, pp. 1121-1127.

[29]

{29} R. A. Brooks, "A robust layered control system for a mobile robot," IEEE J. Robotics Automat., vol. RA-2, pp. 14-23, Mar. 1986.

[30]

{30} R. A. Brooks, "Planning is just a way of avoiding figuring out what to do next," Working Paper 303, Massachusetts Institute of Technology, Artificial Intelligence Laboratory, Sept. 1987.

[31]

{31} D. W. Payton, J. K. Rosenblatt, and D. M. Keirsey, "Plan guided reaction, IEEE Trans. Syst., Man, Cybern., vol. 20, Nov./Dec. 1990.

[32]

{32} J. McCarthy and P. J. Hayes, "Some philosophic problems from the standpoint of artificial intelligence," in Machine Intelligence 4, B. Meltzer and D. Michie, Eds., Edinburgh University Press, 1969, pp. 463-502.

[33]

{33} R.E. Korf, "RealTime heuristic search new results, in Proc. AAAI Conf., 1988.

[34]

{34} C. E. Shannon, "Programming a computer for playing chess," Philosophical Magazine, vol. 41, pp. 256-275, 1950.

[35]

{35} B. Hamidzadeh and S. Shekar, "DYNORA: A Real-time planning algorithm to meet response time constrains in dynamic environments," Proc. Tools for Artificial Intelligence Conf., TAI, 1991.

[36]

{36} B. Bollobas, Random Graphs. New York: Academic, 1985.

[37]

{37} A. Aleliunas, R. M. Karp, R. J. Lipton, L. Lovasz, and C. Rackott, "Random walks, universal traversal sequences and the complexity of maze problems," in Proc. 20th Annu. Symp. Foundations of Computer Science, 1979, pp. 218-223.

Digital Library

[38]

{38} M. R. Garey and D. S. Johnson, "Complexity results for multiprocessor scheduling Under resource constraints," SIAM J. Comput., pp. 397-411, 1975.

Digital Library

[39]

{39} B. Hamidzadeh and S. Shekhar, "Can real-time search algorithms meet deadlines?," in Proc. AAAI Conf., AAAI, 1992.

Cited By

Hadad MKraus SGal YLin R(2019)Temporal Reasoning for a Collaborative Planning Agent in a Dynamic EnvironmentAnnals of Mathematics and Artificial Intelligence10.1023/A:102151262721537:4(331-379)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1023/A%3A1021512627215
Hamidzadeh BKee N(1999)A Dynamic Scheduling BenchmarkProceedings of the 11th IEEE International Conference on Tools with Artificial Intelligence10.5555/850950.853664Online publication date: 8-Nov-1999
https://dl.acm.org/doi/10.5555/850950.853664
Hamidzadeh BAtif YRamamritham K(1999)To Schedule or to ExecuteReal-Time Systems10.1023/A:100800732512916:2/3(281-313)Online publication date: 1-May-1999
https://dl.acm.org/doi/10.1023/A%3A1008007325129

Recommendations

Specification and verification of real-time systems using ACSR-VP
RTCSA '97: Proceedings of the 4th International Workshop on Real-Time Computing Systems and Applications

The reliability of the design of a real-time system is important. For example, when there are errors in avionics control systems or nuclear reactor control systems, the loss of finance, time or even the loss of human lives could be enormous. Therefore ...
Real-time specification patterns
ICSE '05: Proceedings of the 27th international conference on Software engineering

Embedded systems are pervasive and frequently used for critical systems with time-dependent functionality. Dwyer et al have developed qualitative specification patterns to facilitate the specification of critical properties, such as those that must be ...
Specification and Timing Analysis of Real-Time Systems

The correctness of hard real-time systems depends not only on the correct functional behavior but also on the correct temporal behavior. That is, the designed hard real-time system should meet all its functional and timing requirements even in the worst ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Software Engineering

IEEE Transactions on Software Engineering Volume 19, Issue 8

August 1993

95 pages

ISSN:0098-5589

Issue’s Table of Contents

Copyright © Copyright © 1993 IEEE. All Rights Reserved.

Publisher

IEEE Press

Publication History

Published: 01 August 1993

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hadad MKraus SGal YLin R(2019)Temporal Reasoning for a Collaborative Planning Agent in a Dynamic EnvironmentAnnals of Mathematics and Artificial Intelligence10.1023/A:102151262721537:4(331-379)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1023/A%3A1021512627215
Hamidzadeh BKee N(1999)A Dynamic Scheduling BenchmarkProceedings of the 11th IEEE International Conference on Tools with Artificial Intelligence10.5555/850950.853664Online publication date: 8-Nov-1999
https://dl.acm.org/doi/10.5555/850950.853664
Hamidzadeh BAtif YRamamritham K(1999)To Schedule or to ExecuteReal-Time Systems10.1023/A:100800732512916:2/3(281-313)Online publication date: 1-May-1999
https://dl.acm.org/doi/10.1023/A%3A1008007325129

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents