In this paper we present a constraint based strategy for collaborative spatial exploration. Using multiple agents and a set of soft constraints modeled as costs we have developed a collaborative system where each agent chooses its next state optimally with respect to compactness and distance based rules, which can model real-world soft constraints. Using random successor state reordering, this exploration system is capable to obtain a stochastic behavior, yet keeping the path planning optimality at each time step. The constraints are imposed at each time step by using graph search algorithms for planning the route to determine the next location that should be visited by the intelligent agent.

Keywords: Autonomous agents, Cooperative systems, Intelligent robots, Mobile agents