The multiobjective search model is a framework for solving multi-criteria optimization problems using heuristic search techniques. In this framework, the different non-commensurate optimization criteria are mapped into distinct dimensions of a vector valued cost structure and partial order search techniques are used to determine the set of non-inferior solutions. Multiobjective state space search has been studied and generalizations of algorithms such as A* to the multiobjective framework have been considered. In this paper we address the problem of Ε½ . multiobjective heuristic best-first search of acyclic additive ANDrOR graphs. We establish two results which show that in the multiobjective framework, the task of identifying a non-dominated cost potential solution graph is NP-hard in general. This indicates that by extending popular ANDrOR graph search algorithms such as AO* to the multiobjective framework we will not be able to preserve some of their desirable properties. Under such circumstances, we investigate the task of developing effective algorithms for the multiobjective problem and present a linear space ANDrOR graph search algorithm called MObj*. Upper bounds on time and space complexities of this algorithm have been presented. It has also been established that when applied to OR graphs, the proposed algorithm is superior to Ε½ the algorithm proposed by Stewart and White Multiobjective A*, J. Assoc. Ε½ . .