Q: Jay, I have no idea where to begin running your program/fiddling around in it. Could you tell me? And is this a simulator or an actual adopt implementation that solves DCOP..because Im not sure about this but Dr. Bhaskar's project seemed to be on a software that simulated the algorithm's execution. A: The code is both a simulator and the adopt implementation. You should be able to execute it using the "startAdopt" script in the "solver" subdirectory. # usage: startAdopt E.g, % ./startAdopt adopt maxcsp-tree MaxCSP.txt --------------------------------------------------------------- Q: Jay, is the problem data that you used for testing your algorithm included in the files that you sent the link to, if so, then where? A: The problem data is now available on the webpage. The filenames look like this template: Problem--___0.4_r e.g., Problem-GraphColor-18_3_3_0.4_r24 indicates a Graph Coloring problem with 18 nodes, 3 colors, link density 3, and example number 24. --------------------------------------------------------------- Q: What is the problem input file format? A: A problem input file has a list of agents, a list of variables, and a list of constraints, where each constraint lists the pairs of unallowed values, or nogoods. AGENT ... VARIABLE ... CONSTRAINT NOGOOD .... Each must be an integer in [0, - 1] for the corresponding variable. The field of a constraint specifies the cost of breaking the constraint. It is optional and defaults to 1. Here is a sample file for a graph coloring problem with 3 agents, 3 variables each assigned to an agent, and two "not equal" constraints. AGENT 1 AGENT 2 AGENT 3 VARIABLE 0 1 3 VARIABLE 1 2 3 VARIABLE 2 3 3 CONSTRAINT 0 2 NOGOOD 0 0 NOGOOD 1 1 NOGOOD 2 2 CONSTRAINT 1 2 NOGOOD 0 0 NOGOOD 1 1 NOGOOD 2 2 --------------------------------------------------------------- Q: How is the DFS tree formed from the input file? A: The DFS tree is formed in a preprocessing step. Various heuristics can be used. In this implementation, I use something that is similar to the Brelaz heuristic. The relevant code can be found in Problem.java (see method priorityTree()). --------------------------------------------------------------- Q: How is the code structured? A: * Simulator.java is the top-level class. It has a variety of jobs including: - coordinating sending messages between different agent threads. Thus, it implements the MessageSender interface. - spawning each agent in a separate thread. The AgentThread objects are stored in the member variable 'Vector agents'. - logging various data - detecting when all threads (agents) have terminated, and then terminating the entire program * AgentThread.java is a thread representing a single agent. It contains a member variable 'Algorithm algorithm', which is the algorithm that will be executed by this thread (agent). * Algorithm.java: An abstract class representing an algorithm. Since an algorithm typically sends and receives messages, this class also implements the MessageSender interface. * Intradopt.java: Extends the abstract Algorithm class. Multiple variables assigned to this agent are handled by creating a pseudoagent for each variable within this agent. Intradopt coordinates message passing between pseudoagents within an agent. Messages sent between pseudoagents within different agents are passed up to Simulator and handled there. * Adopt.java: Implements the Adopt algorithm assuming a single variable. This graphic might be useful: http://www.isi.edu/~modi/adopt/arch.jpg --------------------------------------------------------------- Q: I cannot run your startAdopt script since there is a java command in there that has a classpath that is pointed to /home/modi/teamcore/code/Adopt. I assume this classpath has an association with $1, $2, and $3. (By the way, are these like environment variables?) A: Your classpath should point to the directory where you un-tar'ed the code. Modify the startAdopt script accordingly. $1, $2, $3 are the three arguments to the startAdopt script and are independent of the classpath. They represent . --------------------------------------------------------------- Q: Where would we specify the bounded error in the code? We are trying to test the algorithm in different configurations. A: You can specify the error bound "b" on the command line in the following way: % ./startAdopt adopt-bound2 maxcsp-tree MaxCSP.txt This specifies an error bound of b=2. This means that Adopt is allowed to break 2 constraints above and beyond the minimum number of constraints it would break in the optimal solution (e.g., with b=0).