DEC-POMDPs provide formal models of many cooperative multiagent problems, but their complexity is nondeterministic exponential-time complete in general. We introduce a sub-class of DEC-POMDPs termed 'multiagent expedition ' (MAE). A typical instance consists of an area populated by mobile agents which have no prior knowledge of the area, limited sensing ability, and the outcomes of their actions is uncertain. Success in MAE relies on planning actions that result in high accumulated rewards. We solve an instance of MAE based on collaborative design networks, a 'tightly-coupled' decision-theoretic multiagent graphical model, to demonstrate its generality. We compare our approach to a 'loosely-coupled' decision making paradigm, the recursive modeling method (RMM) and greedy agents in terms of solution quality, scalability and knowledge representation. Experimental results demonstrate significant superior performance of our system in comparison to RMM and greedy agents, and provides insights into drawbacks associated with loosely-coupled systems when dealing with problems such as MAE.