Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Autonomous Agents and Multi-Agent Systems
Published in: Autonomous Agents and Multi-Agent Systems 1/2020

01-04-2020

Semantics and algorithms for trustworthy commitment achievement under model uncertainty

Authors: Qi Zhang, Edmund H. Durfee, Satinder Singh

Published in: Autonomous Agents and Multi-Agent Systems | Issue 1/2020

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We focus on how an agent can exercise autonomy while still dependably fulfilling commitments it has made to another, despite uncertainty about outcomes of its actions and how its own objectives might evolve. Our formal semantics treats a probabilistic commitment as constraints on the actions an autonomous agent can take, rather than as promises about states of the environment it will achieve. We have developed a family of commitment-constrained (iterative) lookahead algorithms that provably respect the semantics, and that support different tradeoffs between computation and plan quality. Our empirical results confirm that our algorithms’ ability to balance (selfish) autonomy and (unselfish) dependability outperforms optimizing either alone, that our algorithms can effectively handle uncertainty about both what actions do and which states are rewarding, and that our algorithms can solve more computationally-demanding problems through judicious parameter choices for how far our algorithms should lookahead and how often they should iterate.
previous article Fast core pricing algorithms for path auction
next article A norm enforcement mechanism for a time-constrained conditional normative framework

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Appendix
Available only for authorised users
Footnotes
1
For completeness, we should note that our semantics is also the probabalistic analogue of logic-based semantics for conditional commitments (Sect. 2). A conditional commitment asserts that a state in \({\varPhi }\) will provably be reached in worlds where the specified conditions hold, but makes no promises when those conditions do not hold. As long as the agent’s actions reach a state in \({\varPhi }\) when the conditions hold, the commitment is satisfied. Analogously, a probabilistic commitment asserts that a state in \({\varPhi }\) will be assuredly be reached whenever one out of the “good” subset of possible histories hold (where the probability of that occurring given the policy \(\pi\) is no less than \(\rho\)), but makes no promises otherwise. So, again analogously, as long as the agent takes actions prescribed by \(\pi\), the commitment is met regardless of whether a state in \({\varPhi }\) is reached in a specific episode.
 
2
We should point out that our earlier paper [43] that considered this Bayesian setting did not impose this constraint, instead insisting that whatever policy adopted from this point on, appended to the policy taken so far, would satisfy the commitment semantics if followed from the initial state. While that weaker constraint generally performed correctly, we identified corner cases where a dishonest commitment provider could exploit that constraint to increase its local reward. The constraint we provide here (also used in our more recent non-Bayesian paper [44]) closes this loophole.
 
3
Our earlier work limited to reward uncertainty exploited this [43].
 
Literature
1.
Agotnes, T., Goranko, V., & Jamroga, W. (2007). Strategic commitment and release in logics for multi-agent systems (extended abstract). Technical Report IfI-08-01, Clausthal University.
2.
Al-Saqqar, F., Bentahar, J., Sultan, K., & El-Menshawy, M. (2014). On the interaction between knowledge and social commitments in multi-agent systems. Applied Intelligence, 41(1), 235–259.CrossRef
3.
Altman, E. (1999). Constrained Markov decision processes (Vol. 7). Boca Raton: CRC Press.MATH
4.
Bannazadeh, H., & Leon-Garcia, A. (2010). A distributed probabilistic commitment control algorithm for service-oriented systems. IEEE Transactions on Network and Service Management, 7(4), 204–217.CrossRef
5.
Castelfranchi, C. (1995). Commitments: From individual intentions to groups and organizations. In Proceedings of the international conference on multiagent systems (pp. 41–48).
6.
Chesani, F., Mello, P., Montali, M., & Torroni, P. (2013). Representing and monitoring social commitments using the event calculus. Autonomous Agents and Multi-Agent Systems, 27(1), 85–130.CrossRef
7.
Cohen, P. R., & Levesque, H. J. (1990). Intention is choice with commitment. Artificial Intelligence, 42(2–3), 213–261.MathSciNetCrossRef
8.
9.
Dolgov, D., & Durfee, E. (2005). Stationary deterministic policies for constrained MDPs with multiple rewards, costs, and discount factors. In International joint conference on artificial intelligence (Vol. 19, pp. 1326–1331).
10.
Dolgov, D. A., & Durfee, E. H. (2004). Optimal resource allocation and policy formulation in loosely-coupled Markov decision processes. In Proceedings of the fourteenth international conference on automated planning and scheduling (pp. 315–324).
11.
Durfee, E. H., & Singh, S. (2016). On the trustworthy fulfillment of commitments. In Autonomous agents and multiagent systems: AAMAS 2016 workshops best papers. (pp. 1–13). Springer lecture notes in artificial intelligence (2016). Also in Notes of the AAMAS Workshop on Trust in Agent Societies, May 2016.
12.
Günay, A., Liu, Y., & Zhang, J. (2016). Promoca: Probabilistic modeling and analysis of agents in commitment protocols. Journal of Artificial Intelligence Research, 57, 465–508.MathSciNetCrossRef
13.
Günay, A., Songzheng, S., Liu, Y., & Zhang, J. (2015). Automated analysis of commitment protocols using probabilistic model checking. In Twenty-ninth AAAI conference on artificial intelligence.
14.
15.
Hansen, E. A. (1998). Finite-memory control of partially observable systems. Ph.D. Thesis, University of Massachusetts Amherst.
16.
Jennings, N. R. (1993). Commitments and conventions: The foundation of coordination in multi-agent systems. The Knowledge Engineering Review, 8(3), 223–250.MathSciNetCrossRef
17.
Kaelbling, L. P., Littman, M. L., & Cassandra, A. R. (1998). Planning and acting in partially observable stochastic domains. Artificial Intelligence, 101(1–2), 99–134.MathSciNetCrossRef
18.
Maheswaran, R. T., Szekely, P., Becker, M., Fitzpatrick, S., Gati, G., Jin, J., et al. (2008). Predictability & criticality metrics for coordination in complex environments. In Proceedings of the 7th international joint conference on autonomous agents and multiagent systems (Vol. 2, pp. 647–654).
19.
Mallya, A. U., & Huhns, M. N. (2003). Commitments among agents. IEEE Internet Computing, 7(4), 90–93.CrossRef
20.
21.
Meneguzzi, F., Magnaguagno, M. C., Singh, M. P., Telang, P. R., & Yorke-Smith, N. (2018). Goco: Planning expressive commitment protocols. Autonomous Agents and Multi-Agent Systems, 32(4), 459–502.CrossRef
22.
Meneguzzi, F., Telang, P. R., & Yorke-Smith, N. (2015). Towards planning uncertain commitment protocols. In Proceedings of the 2015 international conference on autonomous agents and multiagent systems (pp. 1681–1682).
23.
24.
Pereira, R. F., Oren, N., & Meneguzzi, F. (2017). Detecting commitment abandonment by monitoring sub-optimal steps during plan execution. In Proceedings of the 16th conference on autonomous agents and multiagent systems (pp. 1685–1687).
25.
Poupart, P., Malhotra, A., Pei, P., Kim, K. E., Goh, B., & Bowling, M. (2015). Approximate linear programming for constrained partially observable Markov decision processes. In Twenty-ninth AAAI conference on artificial intelligence.
26.
Puterman, M. L. (2014). Markov decision processes: Discrete stochastic dynamic programming. Hoboken: Wiley.MATH
27.
Raffia, H. (1982). The art and science of negotiation. Cambridge: Harvard University Press.
28.
Sandholm, T., & Lesser, V. R. (2001). Leveled commitment contracts and strategic breach. Games and Economic Behavior, 35, 212–270.MathSciNetCrossRef
29.
Santana, P., Thiébaux, S., & Williams, B. (2016). RAO*: An algorithm for chance-constrained POMDP’s. In Thirtieth AAAI conference on artificial intelligence.
30.
Shiryaev, A. N. (1963). On optimum methods in quickest detection problems. Theory of Probability & Its Applications, 8(1), 22–46.MathSciNetCrossRef
31.
Singh, M. P. (1999). An ontology for commitments in multiagent systems. Artificial Intelligence in the Law, 7(1), 97–113.CrossRef
32.
Singh, M. P. (2012). Commitments in multiagent systems: Some history, some confusions, some controversies, some prospects. In The goals of cognition. Essays in honor of Cristiano Castelfranchi (pp. 601–626). London.
33.
Smallwood, R. D., & Sondik, E. J. (1973). The optimal control of partially observable Markov processes over a finite horizon. Operations Research, 21(5), 1071–1088.CrossRef
34.
Smith, T., & Simmons, R. (2004). Heuristic search value iteration for POMDPs. In Proceedings of the 20th conference on uncertainty in artificial intelligence (pp. 520–527).
35.
Sultan, K., Bentahar, J., & El-Menshawy, M. (2014). Model checking probabilistic social commitments for intelligent agent communication. Applied Soft Computing, 22, 397–409.CrossRef
36.
Telang, P. R., Meneguzzi, F., & Singh, M. P. (2013). Hierarchical planning about goals and commitments. In Proceedings of the 2013 international conference on autonomous agents and multiagent systems (pp. 877–884).
37.
Vokrínek, J., Komenda, A., & Pechoucek, M. (2009). Decommitting in multi-agent execution in non-deterministic environment: Experimental approach. In 8th international joint conference on autonomous agents and multiagent systems (pp. 977–984).
38.
Winikoff, M. (2006). Implementing flexible and robust agent interactions using distributed commitment machines. Multiagent and Grid Systems, 2(4), 365–381.CrossRef
39.
Witwicki, S. J., & Durfee, E. H. (2009). Commitment-based service coordination. International Journal of Agent-Oriented Software Engineering, 3(1), 59–87.CrossRef
40.
Xing, J., & Singh, M. P. (2001). Formalization of commitment-based agent interaction. In Proceedings of the 2001 ACM symposium on applied computing (pp. 115–120).
41.
Xuan, P., & Lesser, V. R. (2000). Incorporating uncertainty in agent commitments. In Intelligent agents VI. Agent theories, architectures, and languages (pp. 57–70). Springer.
42.
Zhang, Q., Durfee, E. H., & Singh, S. (2018). Challenges in the trustworthy pursuit of maintenance commitments under uncertainty. In Proceedings of the 20th international trust workshop co-located with AAMAS/IJCAI/ECAI/ICML 2018 (pp. 75–86).
43.
Zhang, Q., Durfee, E. H., Singh, S., Chen, A., & Witwicki, S. J. (2016). Commitment semantics for sequential decision making under reward uncertainty. In Proceedings of the twenty-fifth international joint conference on artificial intelligence (pp. 3315–3323).
44.
Zhang, Q., Singh, S., & Durfee, E. (2017). Minimizing maximum regret in commitment constrained sequential decision making. In Twenty-seventh international conference on automated planning and scheduling (pp. 348–356).
Metadata
Title
Semantics and algorithms for trustworthy commitment achievement under model uncertainty
Authors
Qi Zhang
Edmund H. Durfee
Satinder Singh
Publication date
01-04-2020
Publisher
Springer US
Published in
Autonomous Agents and Multi-Agent Systems / Issue 1/2020
Print ISSN: 1387-2532
Electronic ISSN: 1573-7454
DOI
https://doi.org/10.1007/s10458-020-09443-0

Other articles of this Issue 1/2020

Autonomous Agents and Multi-Agent Systems 1/2020 Go to the issue

OriginalPaper

Applying Max-sum to asymmetric distributed constraint optimization problems

OriginalPaper

Privacy sensitive environment re-decomposition for junction tree agent organization construction

OriginalPaper

Solving the fair electric load shedding problem in developing countries

OriginalPaper

The complexity of bribery and control in group identification

OriginalPaper

Learning multi-agent communication with double attentional deep reinforcement learning

OriginalPaper

Strategyproof and fair matching mechanism for ratio constraints

Premium Partner

    Image Credits