Ý nghĩa và thuật toán cho việc đạt được cam kết đáng tin cậy dưới sự không chắc chắn của mô hình

Springer Science and Business Media LLC - Tập 34 - Trang 1-35 - 2020
Qi Zhang1, Edmund H. Durfee1, Satinder Singh1
1Computer Science and Engineering, University of Michigan, Ann Arbor, USA

Tóm tắt

Chúng tôi tập trung vào cách một tác nhân có thể thực hiện quyền tự chủ trong khi vẫn đáng tin cậy hoàn thành những cam kết mà nó đã đưa ra với người khác, mặc dù phải đối mặt với sự không chắc chắn về kết quả của các hành động của nó và cách mục tiêu của chính nó có thể phát triển. Ngữ nghĩa chính thức của chúng tôi xem một cam kết xác suất như là những ràng buộc đối với các hành động mà một tác nhân tự chủ có thể thực hiện, thay vì như những lời hứa về những trạng thái của môi trường mà nó sẽ đạt được. Chúng tôi đã phát triển một họ thuật toán tìm kiếm nhìn tới (lookahead) bị ràng buộc cam kết (lặp lại) mà chứng minh tôn trọng ngữ nghĩa, và hỗ trợ các khoản trao đổi khác nhau giữa tính toán và chất lượng kế hoạch. Kết quả thực nghiệm của chúng tôi xác nhận khả năng của các thuật toán trong việc cân bằng giữa tự chủ (ích kỷ) và tính đáng tin cậy (không ích kỷ) vượt trội hơn so với việc tối ưu hóa từng yếu tố riêng biệt, rằng các thuật toán của chúng tôi có thể xử lý hiệu quả sự không chắc chắn về cả hành động nào có hiệu quả và trạng thái nào là có phần thưởng, và rằng các thuật toán của chúng tôi có thể giải quyết những vấn đề yêu cầu tính toán nhiều hơn thông qua các lựa chọn tham số hợp lý cho việc nhìn tới bao xa và lặp lại bao nhiêu lần.

Từ khóa


Tài liệu tham khảo

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. 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. Altman, E. (1999). Constrained Markov decision processes (Vol. 7). Boca Raton: CRC Press. 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. Castelfranchi, C. (1995). Commitments: From individual intentions to groups and organizations. In Proceedings of the international conference on multiagent systems (pp. 41–48). 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. Cohen, P. R., & Levesque, H. J. (1990). Intention is choice with commitment. Artificial Intelligence, 42(2–3), 213–261. CPLEX: IBM ILOG CPLEX 12.1. https://www.ibm.com/analytics/cplex-optimizer. 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). 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). 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. 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. 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. Gurobi: Gurobi 8.1. http://www.gurobi.com/products/gurobi-optimizer. Hansen, E. A. (1998). Finite-memory control of partially observable systems. Ph.D. Thesis, University of Massachusetts Amherst. Jennings, N. R. (1993). Commitments and conventions: The foundation of coordination in multi-agent systems. The Knowledge Engineering Review, 8(3), 223–250. 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. 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). Mallya, A. U., & Huhns, M. N. (2003). Commitments among agents. IEEE Internet Computing, 7(4), 90–93. MATLAB: MATLAB optimization toolbox. https://www.mathworks.com/products/optimization.html. 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. 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). OPTI: OPTI toolbox v2.2. https://www.inverseproblem.co.nz/OPTI. 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). 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. Puterman, M. L. (2014). Markov decision processes: Discrete stochastic dynamic programming. Hoboken: Wiley. Raffia, H. (1982). The art and science of negotiation. Cambridge: Harvard University Press. Sandholm, T., & Lesser, V. R. (2001). Leveled commitment contracts and strategic breach. Games and Economic Behavior, 35, 212–270. Santana, P., Thiébaux, S., & Williams, B. (2016). RAO*: An algorithm for chance-constrained POMDP’s. In Thirtieth AAAI conference on artificial intelligence. Shiryaev, A. N. (1963). On optimum methods in quickest detection problems. Theory of Probability & Its Applications, 8(1), 22–46. Singh, M. P. (1999). An ontology for commitments in multiagent systems. Artificial Intelligence in the Law, 7(1), 97–113. 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. 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. 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). Sultan, K., Bentahar, J., & El-Menshawy, M. (2014). Model checking probabilistic social commitments for intelligent agent communication. Applied Soft Computing, 22, 397–409. 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). 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). Winikoff, M. (2006). Implementing flexible and robust agent interactions using distributed commitment machines. Multiagent and Grid Systems, 2(4), 365–381. Witwicki, S. J., & Durfee, E. H. (2009). Commitment-based service coordination. International Journal of Agent-Oriented Software Engineering, 3(1), 59–87. 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). Xuan, P., & Lesser, V. R. (2000). Incorporating uncertainty in agent commitments. In Intelligent agents VI. Agent theories, architectures, and languages (pp. 57–70). Springer. 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). 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). 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).