State minimization of combinatorial filters is a fundamental problem that arises, for example, in building cheap, resource-efficient robots. But exact minimization is known to be NP-hard. This paper conducts a more nuanced analysis of this hardness than up till now, and uncovers two factors which contribute to this complexity. We show each factor is a distinct source of the problem's hardness and are able, thereby, to shed some light on the role played by (1) structure of the graph that encodes compatibility relationships, and (2) determinism-enforcing constraints. Just as a line of prior work has sought to introduce additional assumptions and identify sub-classes that lead to practical state reduction, we next use this new, sharper understanding to explore special cases for which exact minimization is efficient. We introduce a new algorithm for constraint repair that applies to a large sub-class of filters, subsuming three distinct special cases for which the possibility of optimal minimization in polynomial time was known earlier. While the efficiency in each of these three cases previously appeared to stem from seemingly dissimilar properties, when seen through the lens of the present work, their commonality now becomes clear. We also provide entirely new families of filters that are efficiently reducible.

The problem of combinatorial filter reduction arises from resource optimization in robots; it is one specific way in which automation can help to achieve minimalism, to build better robots. This paper contributes a new definition of filter minimization that is broader than its antecedents, allowing filters (input, output, or both) to be nondeterministic. This changes the problem considerably. Nondeterministic filters may re-use states to obtain more ‘behavior’ per vertex. We show that the gap in size can be significant (larger than polyno-mial), suggesting such cases will generally be more challenging than deterministic problems. Indeed, this is supported by the core complexity result established in this paper: producing nondeterministic minimizers is PSPACE-hard. The hardness separation for minimization existing between deterministic filter and automata, thus, fails to hold for the nondeterministic case.

Reduction of combinatorial filters involves compressing state representations that robots use. Such optimization arises in automating the construction of minimalist robots. But exact combinatorial filter reduction is an NP-complete problem and all current techniques are either inexact or formalized with exponentially many constraints. This paper proposes a new formalization needing only a polynomial number of constraints, and characterizes these constraints in three different forms: nonlinear, linear, and conjunctive normal form. Empirical results show that constraints in conjunctive normal form capture the problem most effectively, leading to a method that outperforms the others. Further examination indicates that a substantial proportion of constraints remain inactive during iterative filter reduction. To leverage this observation, we introduce just-in-time generation of such constraints, which yields improvements in efficiency and has the potential to minimize large filters.

Whether a robot can perform some specific task depends on several aspects, including the robot's sensors and the plans it possesses. We are interested in search algorithms that treat plans and sensor designs jointly, yielding solutions-i.e., plan and sensor characterization pairs-if and only if they exist. Such algorithms can help roboticists explore the space of sensors to aid in making design trade-offs. Generalizing prior work where sensors are modeled abstractly as sensor maps on p-graphs, the present paper increases the potential sensors which can be sought significantly. But doing so enlarges a problem currently on the outer limits of being considered tractable. Toward taming this complexity, two contributions are made: (1) we show how to represent the search space for this more general problem and describe data structures that enable whole sets of sensors to be summarized via a single special representative; (2) we give a means by which other structure (either task domain knowledge, sensor technology or fabrication constraints) can be incorporated to reduce the sets to be enumerated. These lead to algorithms that we have implemented and which suffice to solve particular problem instances, albeit only of small scale. Nevertheless, the algorithm aids in helping understand what attributes sensors must possess and what information they must provide in order to ensure a robot can achieve its goals despite non-determinism.

Information sharing is critical to multi-agent team for cooperative decision making in dynamic and partially observable environments. Other than building a full information coverage, if agents in a team can be self-directed to valuate a potential receiver and where to communicate, the coordination efficiency will be greatly enhanced. Although intensive studies of information valuation approaches have been developed in ontology graph matching and natural language processing, these models fail to perform fast reasoning for large-scale decentralized agents dynamic coordination. In this paper, we propose a fast information valuation approach based on a complex network graph model, which helps to indicate the information importance. Similar to vague information valuation by human, the key is that important information always significantly changes their complex information graph with its incorporation. Therefore, we calculate the semantic based value of this new information in a graph model and build a local graph evaluation algorithm to estimate information graph evolution, instead of performing expensive complete graph search. The advantage is that the local valuation algorithm can be easily transformed into efficient queries in agents' information base so that they can make fast decisions. Although the decision may not be precise, similar to human communication, the information sharing performance is good enough to disseminate valuable information in the multi-agent team. We demonstrate the feasibility of the proposed information valuation approach in a multi-agent cooperation case study.

Sharing information is critical to large teamwork for cooperative decision making in dynamic and partially observable environments. To be effective, other than building a full information coverage, agents should valuate how a potential receiver could be benefited with a piece of given information. In this paper, we propose a fast valuation model with complex network based graph modeling and analysis, which help to indicate the information importance to a given information base. Similar to vague information valuation by humans, the key is that important information always significantly changes their complex information graph with its incorporation. Therefore, we calculate the semantic based value of this new information in a graph model and build a local graph evaluation algorithm to estimate information graph evolution, instead of performing expensive complete graph search. Although the decision may be not precise, similar to human communication, it is good enough to disseminate valuable information around the team.