Removing Redundant Conflict Value Assignments in Resolvent Based Nogood Learning

Taking advantages of popular Resolvent-based (Rslv) and Minimum conflict set (MCS) nogood learning, we propose two new techniques: Unique nogood First Resolvent-based (UFRslv) and Redundant conflict value assignment Free Resolvent-based (RFRslv) nogood learning. By removing conflict value assignments that are redundant, these two new nogood learning techniques can obtain shorter and more efficient nogoods than Rslv nogood learning, and consume less computation effort to generate nogoods than MCS nogood learning. We implement the new techniques in two modern distributed constraint satisfaction algorithms, nogood based asynchronous forward checking (AFCng) and dynamic ordering for asynchronous backtracking with nogood-triggered heuristic (ABT-DOng). Comparing against Rslv and MCS on random distributed constraint satisfaction problems and distributed Langford's problems, UFRslv and RFRslv are favourable in number of messages and NCCCSOs (nonconcurrent constraint checks and set operations) as metrics.