NDLI: The complexity of agent design problems: Determinism and history dependence

Content Provider	Springer Nature Link
Author	Dunne, Paul E. Wooldridge, Michael
Copyright Year	2006
Abstract	The agent design problem is as follows: given a specification of an environment, together with a specification of a task, is it possible to construct an agent that can be guaranteed to successfully accomplish the task in the environment? In this article, we study the computational complexity of the agent design problem for tasks that are of the form “achieve this state of affairs” or “maintain this state of affairs.” We consider three general formulations of these problems (in both non-deterministic and deterministic environments) that differ in the nature of what is viewed as an “acceptable” solution: in the least restrictive formulation, no limit is placed on the number of actions an agent is allowed to perform in attempting to meet the requirements of its specified task. We show that the resulting decision problems are intractable, in the sense that these are non-recursive (but recursively enumerable) for achievement tasks, and non-recursively enumerable for maintenance tasks. In the second formulation, the decision problem addresses the existence of agents that have satisfied their specified task within some given number of actions. Even in this more restrictive setting the resulting decision problems are either pspace-complete or np-complete. Our final formulation requires the environment to be history independent and bounded. In these cases polynomial time algorithms exist: for deterministic environments the decision problems are nl-complete; in non-deterministic environments, p-complete.
Ending Page	371
Page Count	29
Starting Page	343
File Format	PDF
ISSN	10122443
e-ISSN	15737470
Journal	Annals of Mathematics and Artificial Intelligence
Issue Number	3-4
Volume Number	45
Language	English
Publisher	Springer Netherlands
Publisher Date	2006-01-04
Publisher Place	Dordrecht
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Languages and software systems (knowledge-based systems, expert systems, etc.) Complexity of computation (including implicit computational complexity) Computer Science Artificial Intelligence (incl. Robotics) Mathematics autonomous agents computational complexity Complexity
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Artificial Intelligence

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

The USP Farmers herding team

A normative programming language for multi-agent organisations

Using agent- and organisation-oriented programming to develop a team of agents for a competitive game

On quantified linear implications

A Singular web service for geometric computations

Exploiting conjunctive queries in description logic programs

Where logic and agents meet

Integrating answer set programming and constraint logic programming

Analyzing restricted fragments of the theory of linear arithmetic

The complexity of agent design problems: Determinism and history dependence

Similar Documents

The USP Farmers herding team

A normative programming language for multi-agent organisations

Using agent- and organisation-oriented programming to develop a team of agents for a competitive game

On quantified linear implications

A Singular web service for geometric computations

Exploiting conjunctive queries in description logic programs

Where logic and agents meet

Integrating answer set programming and constraint logic programming

Analyzing restricted fragments of the theory of linear arithmetic

The complexity of agent design problems: Determinism and history dependence