Arrow Research search

Author name cluster

Pedro Meseguer

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

30 papers
2 author rows

Possible papers

30

AIJ Journal 2015 Journal Article

Speeding up operations on feature terms using constraint programming and variable symmetry

  • Santiago Ontañón
  • Pedro Meseguer

Feature terms are a generalization of first-order terms which have recently received increased attention for their usefulness in structured machine learning, natural language processing and other artificial intelligence applications. One of the main obstacles for their wide usage is that, when set-valued features are allowed, their basic operations (subsumption, unification, and antiunification) have a very high computational cost. We present a Constraint Programming formulation of these operations, which in some cases provides orders of magnitude speed-ups with respect to the standard approaches. In addition, exploiting several symmetries – that often appear in feature terms databases – causes substantial additional savings. We provide experimental results of the benefits of this approach.

Details DOI

JAAMAS Journal 2014 Journal Article

Reusing cost-minimal paths for goal-directed navigation in partially known terrains

  • Carlos Hernández
  • Tansel Uras
  • Pedro Meseguer

Abstract Situated agents frequently need to solve search problems in partially known terrains in which the costs of the arcs of the search graphs can increase (but not decrease) when the agents observe new information. An example of such search problems is goal-directed navigation with the freespace assumption in partially known terrains, where agents repeatedly follow cost-minimal paths from their current locations to given goal locations. Incremental heuristic search is an approach for solving the resulting sequences of similar search problems potentially faster than with classical heuristic search, by reusing information from previous searches to speed up its current search. There are two classes of incremental heuristic search algorithms, namely those that make the \(h\) -values of the current search more informed (such as Adaptive A*) and those that reuse parts of the A* search trees of previous searches during the current search (such as D* Lite). In this article, we introduce Path-Adaptive A* and its generalization Tree-Adaptive A*. Both incremental heuristic search algorithms terminate their searches before they expand the goal state, namely when they expand a state that is on a provably cost-minimal path to the goal. Path-Adaptive A* stores a single cost-minimal path to the goal state (the reusable path), while Tree-Adaptive A* stores a set of cost-minimal paths to the goal state (the reusable tree), and is thus potentially more efficient than Path-Adaptive A* since it uses information from all previous searches and not just the last one. Tree-Adaptive A* is the first incremental heuristic search algorithm that combines the principles of both classes of incremental heuristic search algorithms. We demonstrate experimentally that both Path-Adaptive A* and Tree-Adaptive A* can be faster than Adaptive A* and D* Lite, two state-of-the-art incremental heuristic search algorithms for goal-directed navigation with the freespace assumption.

Details DOI

ECAI Conference 2012 Conference Paper

A Novel Way to Connect BnB-ADOPT+, with Soft AC

  • Patricia Gutierrez
  • Pedro Meseguer

Combining BnB-ADOPT+, with AC and FDAC levels of soft arc consistency (SAC) improves efficiency for optimal DCOP solving. However, it seems difficult in distributed context to achieve the higher consistency level EDAC, especially considering privacy. As alternative, we propose DAC by token passing. Agents receiving a token ask neighbors for cost extensions. When deletions or Cφ increments occur, the token is passed to neighbor agents. This strategy turns out to be more efficient than FDAC when combined with BnB-ADOPT+, improving communication and specially computation.

Details

AAMAS Conference 2012 Conference Paper

Global Constraints in Distributed Constraint Satisfaction

  • Christian Bessiere
  • Ismel Brito
  • Patricia Gutierrez
  • Pedro Meseguer

Global constraints have been crucial for the success of centralized constraint programming. Here, we propose the inclusion of global constraints in distributed constraint satisfaction. We show how this inclusion can be done, considering different decompositions for global contraints. We provide experimental evidence of their benefits on several benchmarks solved with the ABT algorithm.

PDF

AAMAS Conference 2012 Conference Paper

Improving BnB-ADOPT + -AC

  • Patricia Gutierrez
  • Pedro Meseguer

Several multiagent tasks can be formulated and solved as DCOPs. BnB-ADOPT + -AC is one of the most efficient algorithms for optimal DCOP solving. It is based on BnB-ADOPT, removing redundant messages and maintaining soft arc consistency during search. In this paper, we present several improvements for this algorithm, namely (i) a better implementation (ii) processing exactly simultaneous deletions and (iii) searching on arc consistent cost functions. We present empirical results showing the benefits of these improvements on several benchmarks.

PDF

ECAI Conference 2012 Conference Paper

Speeding Up 2-way Number Partitioning

  • Jesús Cerquides
  • Pedro Meseguer

Several algorithms exist for optimally solving 2-way number partitioning. When the cardinality of the multiset to partition is high enough, solving algorithms have to relay on search techniques with low memory complexity. Currently, CKK is the reference of such algorithms. Here we propose a contribution to speed-up CKK. We detail how to consider terminal nodes with 4, 5, 6 or more numbers left, when the original CKK considers a node terminal when it contains 4 or less numbers left. Using this idea, we propose new CKK implementations, which provide savings up to 70% of execution time with respect to the original CKK algorithm. We provide experimental evidence of the benefits of this approach on random number partitioning instances with numbers of 35 bits.

Details

AAMAS Conference 2011 Conference Paper

Communication-Constrained DCOPs: Message Approximation in GDL with Function Filtering

  • Marc Pujol-Gonzalez
  • Jesus Cerquides
  • Pedro Meseguer
  • Juan Antonio Rodriguez-Aguilar

In this paper we focus on solving DCOPs in communication constrained scenarios. The GDL algorithm optimally solves DCOP problems, but requires the exchange of exponentially large messages which makes it impractical in such settings. Function filtering is a technique that alleviates this high communication requirement while maintaining optimality. Function filtering involves calculating approximations of the exact cost functions exchanged by GDL. In this work, we explore different ways to compute such approximations, providing a novel method that empirically achieves significant communication savings.

PDF

IJCAI Conference 2011 Conference Paper

Distributed Constraint Optimization Problems Related with Soft Arc Consistency

  • Patricia Gutierrez
  • Pedro Meseguer

Distributed Constraint Optimization Problems (DCOPs) can be optimally solved by distributed search algorithms, such as ADOPT and BnB-ADOPT. In centralized solving, maintaining soft arc consistency during search has proved to be beneficial for performance. In this thesis we aim to explore the maintenance of different levels of soft arc consistency in distributed search when solving DCOPs.

PDF Details DOI

IJCAI Conference 2011 Conference Paper

Generalizing ADOPT and BnB-ADOPT

  • Patricia Gutierrez
  • Pedro Meseguer
  • William Yeoh

ADOPT and BnB-ADOPT are two optimal DCOP search algorithms that are similar except for their search strategies: the former uses best-first search and the latter uses depth-first branch-and-bound search. In this paper, we present a new algorithm, called ADOPT(k), that generalizes them. Its behavior depends on the k parameter. It behaves like ADOPT when k = 1, like BnB-ADOPT when k = &infin; and like a hybrid of ADOPT and BnB-ADOPT when 1 < k < &infin; . We prove that ADOPT(k) is a correct and complete algorithm and experimentally show that ADOPT(k) outperforms ADOPT and BnB-ADOPT on several benchmarks across several metrics.

PDF Details DOI

AAMAS Conference 2011 Conference Paper

Tree Adaptive A*

  • Carlos Hern
  • aacute; ndez
  • Xiaoxun Sun
  • Sven Koenig
  • Pedro Meseguer

Incremental heuristic search algorithms can solve sequences of similar search problems potentially faster than heuristic search algorithms that solve each search problem from scratch. So far, there existed incremental heuristic search algorithms (such as Adaptive A*) that make the h-values of the current A* search more informed, which can speed up future A* searches, and incremental heuristic search algorithms (such as D* Lite) that change the search tree of the current A* search to the search tree of the next A* search, which can be faster than constructing it from scratch. In this paper, we present Tree Adaptive A*, which applies to goal-directed navigation in unknown terrain and builds on Adaptive A* but combines both classes of incremental heuristic search algorithms in a novel way. We demonstrate experimentally that it can run faster than Adaptive A*, Path Adaptive A* and D* Lite, the top incremental heuristic search algorithms in the context of goal-directed navigation in unknown grids.

PDF

ECAI Conference 2010 Conference Paper

BnB-ADOPT + with Several Soft Arc Consistency Levels

  • Patricia Gutierrez
  • Pedro Meseguer

Distributed constraint optimization problems can be solved by BnB-ADOPT +, a distributed asynchronous search algorithm. In the centralized case, local consistency techniques applied to constraint optimization have been shown very beneficial to increase performance. In this paper, we combine BnB-ADOPT + with different levels of soft arc consistency, propagating unconditional deletions caused by either the enforced local consistency or by distributed search. The new algorithm maintains BnB-ADOPT + optimality and termination. In practice, this approach decreases substantially BnB-ADOPT + requirements in communication cost and computation effort when solving commonly used benchmarks.

Details

AAMAS Conference 2010 Conference Paper

Improving DPOP with Function Filtering

  • Ismel Brito
  • Pedro Meseguer

DPOP is an algorithm for distributed constraint optimization whichhas, as main drawback, the exponential size of some of its messages. Recently, some algorithms for distributed cluster tree elimination have been proposed. They also suffer from exponential sizemessages. However, using the strategy of cost function filtering, in practice these algorithms obtain important reductions in maximum message size and total communication cost. In this paper, we explain the relation between DPOP and these algorithms, andshow how cost function filtering can be combined with DPOP. Wepresent experimental evidence of the benefits of this new approach.

PDF

ICAPS Conference 2009 Conference Paper

Path-Adaptive A* for Incremental Heuristic Search in Unknown Terrain

  • Carlos Hernández Ulloa
  • Pedro Meseguer
  • Xiaoxun Sun
  • Sven Koenig

Adaptive A* is an incremental version of A* that updates the h-values of the previous A* search to make them more informed and thus future A* searches more focused. In this paper, we show how the A* searches performed by Adaptive A* can reuse part of the path of the previous search and terminate before they expand a goal state, resulting in Path-Adaptive A*. We demonstrate experimentally that Path-Adaptive A* expands fewer states per search and runs faster than Adaptive A* when solving path-planning problems in initially unknown terrain.

Details

IJCAI Conference 2007 Conference Paper

  • Carlos Hern
  • aacute; ndez
  • Pedro Meseguer

We identify some weak points of the LRTA*(k) algorithm in the propagation of heuristic changes. To solve them, we present a new algorithm, LRTA*LS(k), that is based on the selection and up-dating of the interior states of a local space around the current state. It keeps the good theoretical prop-erties of LRTA*(k), while improving substantially its performance. It is related with a lookahead depth greater than 1. We provide experimental evidence of the benefits of the new algorithm on real-time benchmarks with respect to existing approaches.

PDF Details

AIJ Journal 2005 Journal Article

Asynchronous backtracking without adding links: a new member in the ABT family

  • Christian Bessière
  • Arnold Maestre
  • Ismel Brito
  • Pedro Meseguer

Following the pioneer work of Yokoo and colleagues on the ABT (asynchronous backtracking) algorithm, several ABT-based procedures have been proposed for solving distributed constraint networks. They differ in the way they store nogoods, but they all use additional communication links between unconnected agents to detect obsolete information. In this paper, we propose a new asynchronous backtracking algorithm which does not need to add links between initially unconnected agents. To make the description simpler and to facilitate the comparisons between algorithms, we present a unifying framework from which the new algorithm we propose, as well as existing ones, are derived. We provide an experimental evaluation of these algorithms.

Details DOI

AIJ Journal 2002 Journal Article

On forward checking for non-binary constraint satisfaction

  • Christian Bessière
  • Pedro Meseguer
  • Eugene C. Freuder
  • Javier Larrosa

Solving non-binary constraint satisfaction problems, a crucial challenge today, can be tackled in two different ways: translating the non-binary problem into an equivalent binary one, or extending binary search algorithms to solve directly the original problem. The latter option raises some issues when we want to extend definitions written for the binary case. This paper focuses on the well-known forward checking algorithm, and shows that it can be generalized to several non-binary versions, all fitting its binary definition. The classical non-binary version, proposed by Van Hentenryck, is only one of these generalizations.

Details DOI

AIJ Journal 1999 Journal Article

Maintaining reversible DAC for Max-CSP

  • Javier Larrosa
  • Pedro Meseguer
  • Thomas Schiex

We introduce an exact algorithm for maximizing the number of satisfied constraints in an overconstrained CSP (Max-CSP). The algorithm, which can also solve weighted CSP, probabilistic CSP and other similar problems, is based on directed arc-inconsistency counts (DAC). The usage of DAC increases the lower bound of branch and bound based algorithms for Max-CSP, improving their efficiency. Originally, DAC were defined following a static variable ordering. In this paper, we relax this condition, showing how DAC can be defined from a directed constraint graph. These new graph-based DAC can be effectively used for lower bound computation. Interestingly, any directed constraint graph of the considered problem is suitable for DAC computation, so the selected graph can change dynamically during search, aiming at optimizing the exploitation of directed arc-inconsistencies. In addition, directed arc-inconsistencies are maintained during search, propagating the effect of value pruning. With these new elements we present the PFC maintaining reversible DAC algorithm (PFC-MRDAC), a natural successor of PFC-DAC for Max-CSP. We provide experimental evidence for the superiority of PFC-MRDAC on random and real overconstrained CSP instances, including problems with weighted constraints.

Details DOI

IJCAI Conference 1997 Conference Paper

Interleaved Depth-First Search

  • Pedro Meseguer

In tree search, depth-first search (DFS) often uses ordering successor heuristics. If the heuristic makes a mistake ordering a bad successor (without goals in its subtree) before good ones (with goals in their subtrees), DFS has to unsuccessfully traverse the whole bad subtree before finding a goal. To prevent this useless work, we present a new strategy called interleaved depthfirst search (IDFS), which searches depth-first several subtrees —called active— in parallel. IDFS assumes a single processor on which it interleaves DFS on active subtrees. When IDFS finds a mistake, it traverses partially the bad subtree. IDFS does not reexpand nodes and uses a memory amount linear in search depth (with a bounded number of active subtrees). IDFS outperforms DFS if the heuristic improves from the first to the second tree level. Experimental results on hard solvable problems confirm the practical validity of IDFS.

PDF

IJCAI Conference 1995 Conference Paper

Constraint Satisfaction as Global Optimization

  • Pedro Meseguer
  • Javier Larrosa

We present a optimization formulation for discrete binary CSP, based on the construction of a continuous function A(P) whose global maximum represents the best possible solution for that problem. By the best possible solution we mean either (i) a solution of the problem, if it is solvable, or (ii) a partial solution violating a minimal number of constraints, if the problem is unsolvable. This approach is based on relaxation labeling techniques used to enforce consistency in image interpretation. We have used a projected gradient ascent algorithm to maximize A(P) on the n-queens problem obtaining good results but with a high computational cost. To elude this problem, we have developed a heuristic for variable and value selection inspired in the direction in which A(P) is maximized. We have tested this heuristic with forward checking on several classes of CSP.

PDF

KER Journal 1995 Journal Article

Verification and validation of knowledge-based systems with formal specifications

  • Pedro Meseguer
  • Alun D. Preece

Abstract This paper examines how formal specification techniques can support the verification and validation (V&V) of knowledge-based systems. Formal specification techniques provide levels of description which support both verification and validation, and V&V techniques feed back to assist the development of the specifications. Developing a formal specification for a system requires the prior construction of a conceptual model for the intended system. Many elements of this conceptual model can be effectively used to support V&V. Using these elements, the V&V process becomes deeper and more elaborate, and it produces results of a better quality compared with the V&V activities which can be performed on systems developed without conceptual models. However, we note that there are concerns in using formal specification techniques for V&V, not least being the effort involved in creating the specifications.

Details DOI

IJCAI Conference 1993 Conference Paper

Expert System Validation through Knowledge Base Refinement

  • Pedro Meseguer

Knowledge base (KB) refinement is a suitable technique to support expert system (ES) validation. When used for validation, KB refinement should be guided not only by the number of errors to solve but also by the importance of those errors. Most serious errors should be solved first, even causing other errors of lower importance but assuring a neat validity gain. These are the bases for IMPROVER, a KB refinement tool designed to support ES validation. IMPROVER refines ES for medical diagnosis with this classification of error importance: false negative > false positive > ordering mismatch. IMPROVER is being used to validate a real ES and some empirical results are given.

PDF
v2026.09.13