This paper introduces how human languages can be studied in light of recent development of network theories. There are two directions of exploration. One is to study networks existing in the language system. Various lexical networks can be built based on different relationships between words, being semantic or syntactic. Recent studies have shown that these lexical networks exhibit small-world and scale-free features. The other direction of exploration is to study networks of language users (i.e. social networks of people in the linguistic community), and their role in language evolution. Social networks also show small-world and scale-free features, which cannot be captured by random or regular network models. In the past, computational models of language change and language emergence often assume a population to have a random or regular structure, and there has been little discussion how network structures may affect the dynamics. In the second part of the paper, a series of simulation models of diffusion of linguistic innovation are used to illustrate the importance of choosing realistic conditions of population structure for modeling language change. Four types of social networks are compared, which exhibit two categories of diffusion dynamics. While the questions about which type of networks are more appropriate for modeling still remains, we give some preliminary suggestions for choosing the type of social networks for modeling.

We are given an equal number of mobile robotic agents, and distinct target locations. Each agent has simple integrator dynamics, a limited communication range, and knowledge of the position of every target. We address the problem of designing a distributed algorithm that allows the group of agents to divide the targets among themselves and, simultaneously, leads each agent to reach its unique target. We do not require connectivity of the communication graph at any time. We introduce a novel assignment-based algorithm with the following features: initial assignments and robot motions follow a greedy rule, and distributed refinements of the assignment exploit an implicit circular ordering of the targets. We prove correctness of the algorithm, and give worst-case asymptotic bounds on the time to complete the assignment as the environment grows with the number of agents. We show that among a certain class of distributed algorithms, our algorithm is asymptotically optimal. The analysis utilizes results on the Euclidean traveling salesperson problem.

A Nash Equilibrium (NE) is a strategy profile resilient to unilateral deviations, and is predominantly used in the analysis of multiagent systems. A downside of NE is that it is not necessarily stable against deviations by coalitions. Yet, as we show in this paper, in some cases, NE does exhibit stability against coalitional deviations, in that the benefits from a joint deviation are bounded. In this sense, NE approximates strong equilibrium. Coalition formation is a key issue in multiagent systems. We provide a framework for quantifying the stability and the performance of various assignment policies and solution concepts in the face of coalitional deviations. Within this framework we evaluate a given configuration according to three measures: (i) IR_min: the maximal number alpha, such that there exists a coalition in which the minimal improvement ratio among the coalition members is alpha, (ii) IR_max: the maximal number alpha, such that there exists a coalition in which the maximal improvement ratio among the coalition members is alpha, and (iii) DR_max: the maximal possible damage ratio of an agent outside the coalition. We analyze these measures in job scheduling games on identical machines. In particular, we provide upper and lower bounds for the above three measures for both NE and the well-known assignment rule Longest Processing Time (LPT). Our results indicate that LPT performs better than a general NE. However, LPT is not the best possible approximation. In particular, we present a polynomial time approximation scheme (PTAS) for the makespan minimization problem which provides a schedule with IR_min of 1+epsilon for any given epsilon. With respect to computational complexity, we show that given an NE on m >= 3 identical machines or m >= 2 unrelated machines, it is NP-hard to determine whether a given coalition can deviate such that every member decreases its cost.

For many voting rules, it is NP-hard to compute a successful manipulation. However, NP-hardness only bounds the worst-case complexity. Recent theoretical results suggest that manipulation may often be easy in practice. We study empirically the cost of manipulating the single transferable vote (STV) rule. This was one of the first rules shown to be NP-hard to manipulate. It also appears to be one of the harder rules to manipulate since it involves multiple rounds and since, unlike many other rules, it is NP-hard for a single agent to manipulate without weights on the votes or uncertainty about how the other agents have voted. In almost every election in our experiments, it was easy to compute how a single agent could manipulate the election or to prove that manipulation by a single agent was impossible. It remains an interesting open question if manipulation by a coalition of agents is hard to compute in practice.

Time perception and inferences there from are of critical importance to many autonomous agents. But time is not perceived directly by any sensory organ. We argue that time is constructed by cognitive processes. Here we present a model for time perception that concentrates on succession and duration, and that generates these concepts and others, such as continuity, immediate present duration, and lengths of time. These concepts are grounded through the perceptual process itself. The LIDA cognitive model is used to illustrate these ideas.

Defeasible Logic Programming (DELP) is a formalism that extends declarative programming to capture defeasible reasoning. Its inference mechanism, upon a query on a literal in a program, answers by indicating whether or not it is warranted in an argumentation process. While the properties of DELP are well known, some of its basic elements can be redefined in order to shed light on some of the subtleties of the warrant process. We will discuss these alternative definitions and the cases in which they provide a better performance.

GLAIR (Grounded Layered Architecture with Integrated Reasoning) is a multi-layered cognitive architecture for embodied agents operating in real,virtual, or simulated environments containing other agents. The highest layer of the GLAIR Architecture, the Knowledge Layer (KL), contains the beliefs of the agent, and is the layer in which conscious reasoning, planning, and act selection is performed. The lowest layer of the GLAIR Architecture, the Sensori-Actuator Layer (SAL), contains the controllers of the sensors and effectors of the hardware or software robot. Between the KL and the SAL is the Perceptuo-Motor Layer (PML), which grounds the KL symbols in perceptual structures and subconscious actions, contains various registers for providing the agent's sense of situatedness in the environment, and handles translation and communication between the KL and the SAL. The motivation for the development of GLAIR has been "Computational Philosophy", the computational understanding and implementation of human-level intelligent behavior without necessarily being bound by the actual implementation of the human mind. Nevertheless, the approach has been inspired by human psychology and biology.

Verification that agent communication protocols have desirable properties or do not have undesirable properties is an important issue in agent systems where agents intend to communicate using such protocols. In this paper we explore the use of model checkers to verify properties of agent communication protocols, with these properties expressed as formulae in temporal logic.  We illustrate our approach using a recently-proposed protocol for agent dialogues over commands, a protocol that permits the agents to present questions, challenges and arguments for or against compliance with a command.

The web forum is a key tool in the building of new knowledge among students in Learning Management Systems. Students’ posted messages, in fact, build up a relationship network which supports a collaborative reflection about the forum topic. In this network two interaction levels can be distinguished. The former is the interaction between peers (the students), the latter between students and instructors (teachers and tutors). The role of the second interaction is particularly important as a feedback mechanism in the discussion dynamic but it is subjected to two kinds of limitations. The first one is the huge number of messages that makes difficult, for tutors and teachers, to quickly evaluate the progress of their students and the second one is the subjective bias of the tutors that influence the evaluation. In order to limit these two inefficiencies a multiagent system can be used to monitor such evolution and recognize the state in which the forum is. Such system is based on metrics derived from the textual and social network analysis that, feeding a rule engine, gives the instructor a more objective view of the forum evolution.

Individuals with high-functioning autism spectrum disorders (HFASD) have very individualistic needs, abilities, and are surrounded by very different social contexts. Consequently, special education and therapeutic interventions often need to be adapted to a particular individual. We are interested in developing systems that can help adolescents with HFASD rehearse and learn social skills with reduced aide from parents, guardians, teachers, and therapists. We describe a social skill learning game that utilizes social scenarios. Because of the individualistic needs and abilities of our target users, we describe ongoing work on AI to assist caregivers with the authoring of tailored social scenarios.