Bi-objective search problems are a useful generalization of shortest path search. This paper reviews some recent contributions for the solution of this problem with emphasis on the efficiency of the dominance checks required for pruning, and introduces a new algorithm that improves time efficiency over previous proposals. Experimental results are presented to show the performance improvement using a set of standard problems over bi-objective road maps.

Abstract This paper addresses the problem of approximating the set of all solutions for Multi-objective Markov Decision Processes. We show that in the vast majority of interesting cases, the number of solutions is exponential or even infinite. In order to overcome this difficulty we propose to approximate the set of all solutions by means of a limited precision approach based on White’s multi-objective value-iteration dynamic programming algorithm. We prove that the number of calculated solutions is tractable and show experimentally that the solutions obtained are a good approximation of the true Pareto front.

In this paper we present BH-ShaDe, an educational software tool that assists architecture students in the process of learning to design single-family dwellings. To this end, BH-ShaDe generates and proposes housing units schemes, which can serve as starting points in student´s exercises and projects. The tool has been designed and implemented based on the ideas of reinforcement learning and shape grammars. The students can select the more promising schemes (among those generated by the tool), and then transform them in complete architectural plans, and finally use them to develop a complete residential project. To evaluate the validity of this approach, BH-ShaDe has been tested with 78 architecture students of the University of Málaga. The results have shown that the starting points were suitable, diverse and useful, and that they have helped students to learn how to design residential projects.

This article considers the performance of the MOA* multiobjective search algorithm with heuristic information. It is shown that in certain cases blind search can be more efficient than perfectly informed search, in terms of both node and label expansions. A class of simple graph search problems is defined for which the number of nodes grows linearly with problem size and the number of nondominated labels grows quadratically. It is proved that for these problems the number of node expansions performed by blind MOA* grows linearly with problem size, while the number of such expansions performed with a perfectly informed heuristic grows quadratically. It is also proved that the number of label expansions grows quadratically in the blind case and cubically in the informed case.

This paper studies the complexity of two different algorithms proposed as extensions of A* for multiobjective search: MOA* and NAMOA*. It is known that, for any given problem, NAMOA* requires the consideration of no more alternatives than MOA* when provided with the same heuristic information.

The article describes and analyzes NAMOA * , an algorithm for multiobjective heuristic graph search problems. The algorithm is presented as an extension of A * , an admissible scalar shortest path algorithm. Under consistent heuristics A * is known to improve its efficiency with more informed heuristics, and to be optimal over the class of admissible algorithms in terms of the set of expanded nodes and the number of node expansions. Equivalent beneficial properties are shown to prevail in the new algorithm.

Frontier search is a new search technique that achieves important memory savings over previous best-first search algorithms. This paper describes an extension of frontier search to bicriterion graph search problems that achieves also important memory savings. The new algorithm is evaluated using a set of random problems.

Coalition formation is an important mechanism for cooperation in multiagent systems. In this paper we address the problem of coalition formation among self‐interested agents in superadditive task‐oriented domains. We assume that each agent has some “structure,” i.e., that it can be described by the values taken by a set ofmnonnegative attributes that represent the resourcesweach agent is endowed with. By defining the coalitional value as a functionVofw, we prove a sufficient condition for the existence of a stable payment configuration—in the sense of the core—in terms of certain properties ofV. We apply these ideas to a simple case that can be described by a linear program and show that it is possible to compute for it—in polynomial time—an optimal task allocation and a stable payment configuration.

Abstract In the last few years coalition formation algorithms have been proposed as a possible way of modeling autonomous agent cooperation in multi‐agent systems. This work is based on a previously proposed coalition formation model founded on game theory for a class of task‐oriented problems that guarantees an optimum task allocation and a stable profit division. In this paper we study two properties of the model that are very important for application in real‐life scenarios: robustness and tolerance to an agent's misbehavior. First, we study the robustness of this model as regards the effect the agent's failure has on the resultant profits of the coalition formation. Secondly, we also study the coalition formation model in the presence of misbehaving agents. Agents have some kind of execution autonomy, and they can deceive or mislead each other when they reveal their information, if they believe this will give them more profits. Copyright © 2005 John Wiley & Sons, Ltd.