Abstract
We put forward a general theory of goal-oriented communication, where communication is not an end in itself, but rather a means to achieving some goals of the communicating parties. Focusing on goals provides a framework for addressing the problem of potential “misunderstanding” during communication, where the misunderstanding arises from lack of initial agreement on what protocol and/or language is being used in communication. In this context, “reliable communication” means overcoming any initial misunderstanding between parties towards achieving a given goal. Despite the enormous diversity among the goals of communication, we propose a simple model that captures all goals.
In the simplest form of communication we consider, two parties, a user and a server, attempt to communicate with each other in order to achieve some goal of the user. We show that any goal of communication can be modeled mathematically by introducing a third party, which we call the referee, who hypothetically monitors the conversation between the user and the server and determines whether or not the goal has been achieved. Potential misunderstanding between the players is captured by allowing each player (the user/server) to come from a (potentially infinite) class of players such that each player is unaware which instantiation of the other it is talking to. We identify a main concept, which we call sensing, that allows goals to be achieved even under misunderstanding. Informally, sensing captures the user's ability (potentially using help from the server) to simulate the referee's assessment on whether the communication is achieving the goal. We show that when the user can sense progress, the goal of communication can be achieved despite initial misunderstanding. We also show that in certain settings sensing is necessary for overcoming such initial misunderstanding.
Our results significantly extend the scope of the investigation started by Juba and Sudan (STOC 2008) who studied the foregoing phenomenon in the case of a single specific goal. Our study shows that their main suggestion, that misunderstanding can be detected and possibly corrected by focusing on the goal, can be proved in full generality.
- Babai, L., Fortnow, L., and Lund, C. 1991. Non-deterministic exponential time has two-prover interactive protocols. Computat. Complex. 1, 1, 3--40.Google ScholarCross Ref
- Babai, L., Fortnow, L., Nisan, N., and Wigderson, A.. 1993. BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computat. Complex. 3, 307--318. Google ScholarDigital Library
- Bellare, M. and Goldwasser, S. 1994. The complexity of decision versus search. SIAM J. Comput. 23, 1, 91--119. Google ScholarDigital Library
- Berners-Lee, T., Hendler, J., and Lassila, O. 2001. The semantic web. Scientific American, 34--43.Google Scholar
- Blum, M. and Kannan, S.. 1989. Designing programs that check their work. In Proceedings of the 21st Annual ACM Symp. Theory of Comput. (STOC). 86--97. Google ScholarDigital Library
- Briggs, P., Srivastava, L., and International Telecommunication Union. 2005. The Internet of Things. 7th ITU Internet report. International Telecommunication Union, Geneva.Google Scholar
- Dewey, J. 1929. Experience and Nature. Norton, New York.Google Scholar
- Goldreich, O., Juba, B., and Sudan, M. 2009. A theory of goal-oriented communication. Tech. rep. TR09-075, Electronic Colloquium on Computational Complexity (ECCC).Google Scholar
- Goldreich, O., Micali, S., and Wigderson, A. 1991. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. ACM 38, 3, 691--729. Google ScholarDigital Library
- Goldwasser, S., Micali, M., and Rackoff, C. 1989. The knowledge complexity of interactive proof systems. SIAM J. Comput. 18, 186--208. Google ScholarDigital Library
- Hutter, M. 2004. Universal Artificial Intelligence. Springer, Berlin. Google ScholarDigital Library
- Juba, B. 2011. Universal Semantic Communication. Springer, Berlin. Google ScholarDigital Library
- Juba, B., Kalai, A., Khanna, S., and Sudan, M. 2011. Compression without a common prior: An information-theoretic justification for ambiguity in language. In Proceedings of the 2nd Symposium on Innovations in Computer Science. 79--86.Google Scholar
- Juba, B. and Sudan, M. 2008a. Universal semantic communication I. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), 123--132. Google ScholarDigital Library
- Juba, B. and Sudan, M. 2008b. Universal semantic communication II: A theory of goal-oriented communication. Tech. rep. TR08-095, Electronic Colloquium on Computational Complexity (ECCC).Google Scholar
- Juba, B. and Sudan, M. 2011. Efficient semantic communication via compatible beliefs. In Proceedings of the 2nd Symposium on Innovations in Computer Science. 22--31.Google Scholar
- Juba, B. and Vempala, S. 2011. Semantic communication for simple goals is equivalent to on-line learning. In Proceedings of the 22nd International Conference on Algorithmic Learning Theory. Lecture Notes in Artificial Intelligence Series, vol. 6925, Springer, 277--291. Google ScholarDigital Library
- Lund, C., Fortnow, L., Karloff, H., and Nisan, N. 1992. Algebraic methods for interactive proof systems. J. ACM 39, 4, 859--868. Google ScholarDigital Library
- Malinowski, B. 1923. The problem of meaning in primitive languages. In The Meaning of Meaning, C. K. Ogden and I. A. Richards, Eds. Harcourt Brace Jovanovich, New York.Google Scholar
- Russell, S. and Subramanian, D. 1995. Provably bounded-optimal agents. J. Artif. Intel. Res. 2, 575--609. (Preliminary version with R. Parr in 13th IJCAI, 1993.) Google ScholarDigital Library
- Shamir, A. 1992. IP = PSPACE. J. ACM 39, 4, 869--877. Google ScholarDigital Library
- Shannon, C. 1948. A mathematical theory of communication. Bell Syst. Tech. J. 27, 379--423, 623--656.Google ScholarCross Ref
- Shadbolt, N., Berners-Lee, T., and Hall, W. 2006. The semantic web revisited. IEEE Intelli. Sys. 21, 3, 96--101. Google ScholarDigital Library
- Uckelmann, D., Harrison, M., and Michahelles, F. 2011. An architectural approach towards the future internet of things. In Architecting the Internet of Things, D. Uckelmann, M. Harrison, and F. Michahelles, Eds. Springer, Berlin, 1--24.Google Scholar
- Uckelmann, D., Harrison, M., and Michahelles, F. 2011b. Architecting the Internet of Things. Springer, Berlin. Google ScholarDigital Library
- Wittgenstein, L. 1958. The Blue and Brown Books: Preliminary Studies for the ‘Philosophical Investigations’. Harper & Row, New York.Google Scholar
- Wittgenstein, L. 2001. Philosophical Investigations. Basil Blackwell, Malden.Google Scholar
Index Terms
- A theory of goal-oriented communication
Recommendations
A theory of goal-oriented communication
PODC '11: Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computingWe put forward a general theory of goal-oriented communication, where communication is not an end in itself, but rather a means to achieving some goals of the communicating parties. Focusing on goals provides a framework for addressing the problem of ...
Enabling Goal Oriented Action Planning with Goal Net
WI-IAT '09: Proceedings of the 2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology - Volume 02In this paper, we propose an agent planning system based on the Goal Net model. The agent’s goals are identified and organized in a composite goal hierarchy. Three kinds of relations between goals are defined: choice, concurrency and synchronization. ...
Implementation of a GOAL PROGRAM
SIGUCCS '75: Proceedings of the 3rd annual ACM SIGUCCS conference on User servicesWe all need specific goals to guide us. Goals give you direction. Recognizing that we need goals is the first step toward choosing and achieving those goals.
By making each goal specific, you have definite deadlines to aim for. Get a statement of your ...
Comments