R. Trejo Receives Best Dissertation Award for an Interval-Related Dissertation

The main problem of planning (e.g., robot planning) is to find a sequence of actions that an agent must perform to achieve a given objective. Historically, in Artificial Intelligence (AI), the planning problem was mainly formulated and solved in a deterministic environment, when the initial state is known precisely and when the result of each action in each state is known (and uniquely determined). In many real-life situations, however, the agent does not have complete information about the initial state of the system. In the best case, the agent may know the probabilities of the different properties that describe the state of the system; sometimes even such probabilities are unknown and the agent has no information whatsoever about some parameters of the initial state except for the lower and upper bounds on these parameters (i.e., except for the interval of possible values).

In his dissertation, Raul started with the analysis of the computational complexity of optimal planning under uncertainty. Exact optimization turns out to be computationally intractable, so heuristic approximate methods are needed. Raul developed new such methods (based on interval computations) for planning under probabilistic and interval uncertainty, and he also provided a probabilistic justification for previously proposed heuristic "fuzzy" methods.

In the process of developing interval techniques for optimal planning, Raul overviewed different interval optimization techniques, and propose radical improvements which lead to optimal and sub-optimal interval methods. In particular, in statistical setting, he developed an optimal error estimation algorithm - optimal in the sense that this algorithm requires the smallest amount of computation time to compute the resulting error characteristics. Optimal algorithms of this type, algorithms that cannot be further improved, are extremely rare in computer science, and it is a big accomplishment on behalf of one of our students to have developed such an algorithm. The resulting survey appeared as a chapter in a seminal Handbook published under the editorship of P. Pardalos, one of the world leading specialists in optimization algorithms.

APPENDIX
Publications of Raul A. Trejo related to his dissertation:

BOOK CHAPTER

1 Raul Trejo and Vladik Kreinovich, "Error Estimations for Indirect Measurements: Randomized vs. Deterministic Algorithms For `Black-Box' Programs", Sanguthevar Rajasekaran, Panos Pardalos, John Reif, and Jose Rolim (eds.), Handbook on Randomized Computing, Kluwer, 2001, pp. 673-729.

EDITED PROCEEDINGS

1 Goetz Alefeld and Raul A. Trejo (eds.), Interval Computations and its Applications to Reasoning Under Uncertainty, Knowledge Representation, and Control Theory. Proceedings of MEXICON'98, Workshop on Interval Computations, 4th World Congress on Expert Systems, Mexico City, Mexico, 1998.

JOURNAL PUBLICATIONS

1 Chitta Baral, Vladik Kreinovich, and Raul Trejo, "Computational Complexity of Planning and Approximate Planning in the Presence of Incompleteness", Artificial Intelligence, 2000, Vol. 122, pp. 241-267.

2 Raul A. Trejo, Joel Galloway, Charanjiv Sachar, Vladik Kreinovich, Chitta Baral, and Le Chi Tuan, "From Planning to Searching for the Shortest Plan: An Optimal Transition", International Journal of Uncertainty, Fuzziness, Knowledge-Based Systems (IJUFKS), 2001, Vol. 9, No. 6.

3 Raul Trejo, Vladik Kreinovich, I. R. Goodman, Jesus Martinez, and Reginaldo Gonzalez, "A Realistic (Non-Associative) Logic And a Possible Explanations of 7+-2 Law", International Journal of Approximate Reasoning, 2002, Vol. 29, pp. 235-266.

4 Raul Trejo and Vladik Kreinovich, "Computing the Shape of the Image of a Multi-Linear Mapping Is Possible But Computationally Intractable: Theorems", International Journal of General Systems, 2002, Vol. 31, No. 1, pp. 17-27.

5 Raul A. Trejo, Vladik Kreinovich, and Luc Longpre, "Choosing a Physical Model: Why Symmetries?", Bulletin of the European Association for Theoretical Computer Science (EATCS), 2000, Vol. 70, pp. 159-161.

5 Raul Antonio Trejo Ramirez and Vladik Kreinovich, "How to rate numerical packages? Foundations of ratings, and their possible use in numerical mathematics, in education, and in military design", ACM SIGNUM Newsletter, 1997, Vol. 32, No. 1/2, pp. 2-10.

6 Robert Lea, Vladik Kreinovich, and Raul Trejo, "Optimal interval enclosures for fractionally-linear functions, and their application to intelligent control", Reliable Computing, 1996, Vol. 2, No. 3, pp. 265-286.

PAPERS IN REFEREED CONFERENCE PROCEEDINGS

1 Chitta Baral, Vladik Kreinovich, and Raul A. Trejo, "Computational Complexity of Planning with Temporal Goals", Proceedings of the International Joint Conferences in Artificial Intelligence IJCAI'01, Seattle, Washington, August 4-10, 2001, pp. 509-514. 2 Raul Trejo, Vladik Kreinovich, and Chitta Baral, "Towards Feasible Approach to Plan Checking Under Probabilistic Uncertainty: Interval Methods", Proc. of the 17th National Conference on Artificial Intelligence AAAI'2000, Austin, TX, July 30-August 3, 2000, pp. 545-550.

3 Chitta Baral, Le-Chi Tuan, Raul Trejo, and Vladik Kreinovich, "Computational Complexity of Planning Based on Partial Information About The System's Present and Past States", In: J. Lloyd et al. (eds.), Proceedings of the First International Conference on Computational Logic CL'2000, London, July 24-28, 2000, Springer Lecture Notes in Artificial Intelligence, Vol. 1861, pp. 882-896.

4 Chitta Baral, Vladik Kreinovich, and Raul Trejo, "Computational Complexity of Planning and Approximate Planning in Presence of Incompleteness", Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence IJCAI'99, Stockholm, Sweden, July 31 - August 6, 1999, Vol. 2, pp. 948-953.

5 I. R. Goodman, Raul A. Trejo, Vladik Kreinovich, Jesus Martinez, and Reginaldo Gonzalez, "An even more realistic (non-associative) interval logic and its relation to psychology of human reasoning", Proceedings of the Joint 9th World Congress of the International Fuzzy Systems Association and 20th International Conference of the North American Fuzzy Information Processing Society IFSA/NAFIPS 2001, Vancouver, Canada, July 25-28, 2001, pp. 1586-1591.

6 Richard Alo, Raul Trejo, and Vladik Kreinovich, "Can Computers Do the Job of Nobelist Physicists? Planck Formula Revisited", Proc. of the 2001 International Conference on Information Technology for the New Millennium IConIT'2001, Bangkok, Thailand, May 28-30, 2001, pp. 284-295.

7 Raul A. Trejo, Joel Galloway, Charanjiv Sachar, Vladik Kreinovich, Chitta Baral, and Le Chi Tuan, "From Planning to Searching for the Shortest Plan: An Optimal Transition", Proc. of International Conference on Intelligent Technologies, Bangkok, Thailand, December 13-15, 2000, pp. 17-23.

8 Raul Trejo and Vladik Kreinovich, "Complexity of Collective Decision Making Explained by Neural Network Universal Approximation Theorem", In: Goetz Alefeld and Raul A. Trejo (eds.), Interval Computations and its Applications to Reasoning Under Uncertainty, Knowledge Representation, and Control Theory. Proceedings of MEXICON'98, Workshop on Interval Computations, 4th World Congress on Expert Systems, Mexico City, Mexico, 1998.

9 Vladik Kreinovich and Raul Trejo, "Optimal interval computation techniques: optimization of numerical methods in case of uncertainty", In: Marcilia A. Campos (ed.), Abstracts of the II Workshop on Computer Arithmetic, Interval and Symbolic Computation (WAI'96), Recife, Pernambuco, Brazil, August 7-8, 1996, pp. 48-50.

Back to Honors Received by Interval Researchers

Back to the main menu of the Interval Computations website