Show 40 post(s) from this thread on one page
Page 1 of 2 12 Last
• September 29th, 2011, 03:11 PM
Zaxx81
Writing a Depth-Limited Search Java Class in an Artificial Intelligence course. I have included the code for my class below and attached a flow diagram I came up with. This project is based on the "Vacuum World" problem in 'Artificial Intelligence: A Modern Approach'.

The class compiles and runs correctly with all the other classes and packages. Those files are instructor provided and work with a Breadth-First Search Class he included. The program successfully finds the goal state and returns the goal state to the user if the program starts in the goal state. Additionally, the program successfully transverses through the search space using DLS and finds a goal state. I used the println in the recursive method to show that it finds a goal state.

What I am having problem with is the recursion. When I use the recursion backtracking to find a "goal state", the program finds the goal state, however, it keeps searching the searchspace. What I need help with is when it finds a "goal state", I need the program and all previously threaded recursion calls to stop and return the first found "goal state".

If needed I can upload all of the files when I get off of work. But I hope it's an easy answer.

Code :

```package ai.searches;   import ai.Problem; import ai.Solution; import ai.Successor; import dataStructures.Iterator; import dataStructures.List;   public class DepthLimitedSearch extends AbstractSearch { int depthLimit;   public DepthLimitedSearch(Problem p, int maxDepth) { super(p); this.depthLimit = maxDepth; }   public Solution search() { // stores the solution to return Solution solution = null; Successor solutionNode = null;   solutionNode = recursiveExpandNode( (Successor)problem.getInitialState() );   if( solutionNode != null ) solution = new Solution( solutionNode, solutionNode.getDepth() );   return solution; }   private Successor recursiveExpandNode( Successor node ) { Successor output = null;   // check for goal state if( problem.isGoalState( node.getState() ) ) { System.out.println( "Yes"); return node; }   // check for depth if( node.getDepth() > ( this.depthLimit - 1 ) ) return null;   List successorsList = problem.getSuccessorFunction().getSuccessors(node);   if( !successorsList.isEmpty() ) { for( Iterator itr = successorsList.iterator(); itr.hasNext(); itr.next() ) { // get current Successor Successor current = (Successor)itr.getCurrent();   // set parent current.setParent( node );   // set depth current.setDepth(node.getDepth() + 1);   System.out.println( current.toString() );   // recursively expands search space output = recursiveExpandNode( current ); if( problem.isGoalState( current.getState() ) ) break; } } return output; } }```
• September 29th, 2011, 03:26 PM
Norm
Quote:

What I need help with is when it finds a "goal state", I need the program and all previously threaded recursion calls to stop and return the first found "goal state".
Can you use what the method returns to tell the caller that the goal has been found and to stop further searching and to return that results to its caller?
• September 29th, 2011, 05:02 PM
dabdi
I think your termination criteria is wrong. You should unwind the recursion when a goal is found anywhere in the tree (not just when the current node is a goal). A simple solution is to have a Boolean member variable that signals a goal is found somewhere, and then return from every node when that is set. For more complex goals with a range of values, you may need to keep track of the best values at each internal node.
• September 29th, 2011, 08:38 PM
Zaxx81
Yep, I am not terminating properly. If someone would please provide some code to try that would be awesome.
• September 29th, 2011, 08:46 PM
Norm
Can you provide a small program that compiles and executes to demonstrate your problem?
Your posted code is incomplete and uses 3rd party classes.
• October 1st, 2011, 12:01 PM
Zaxx81
Quote:

Originally Posted by Norm
Can you provide a small program that compiles and executes to demonstrate your problem?
Your posted code is incomplete and uses 3rd party classes.

Attached is the source code for the entire program. The class I am working on is in src > ai > searches > DepthLimitedSearch.java and the main class is src > VacuumWorld > VacuumWorldDriver.java

Attachment 772
• October 1st, 2011, 12:24 PM
Norm
There are 76 source files in that zip. What do you expect anyone to do with all that code?
• October 1st, 2011, 12:54 PM
Zaxx81
Executable code was requested. I am only struggleing with one method in one class. As mentioned above I am having problems terminating all recursive branches when a goal state is found. The method is called recursiveExpandNode(), see details in my initial post above.
• October 1st, 2011, 01:09 PM
dabdi
Quote:

Originally Posted by Zaxx81
Executable code was requested. I am only struggleing with one method in one class. As mentioned above I am having problems terminating all recursive branches when a goal state is found. The method is called recursiveExpandNode(), see details in my initial post above.

Did you try my suggestion ? It is pretty straight forward and I can not see why it will not work.
Declare a member variable goalFound.
Code java:

`Boolean goalFound;`
Set it to false initially (in constructor)
Code java:

`goalFound = false;`
Then wherever you test for termination (isGoalState(node)) , do the following instead
Code java:

```if(goalFound || problem.isGoalState( node.getState() ) ) { System.out.println( "Yes"); goalFound = true; return node; }```
• October 1st, 2011, 01:14 PM
Norm
I don't see many printlns for debugging in that code. How are you debugging it?
• October 1st, 2011, 01:33 PM
Zaxx81
Gonna try the boolean idea after lunch. Attached is a flow diagram for just that method. The problem is when a recursive node is terminated, the previous recursive branch is still in the "for loop", so it goes to the next successor in the List.

There is a println inside the recursiveExpandNode. The print shows that it finds and recognizes the goal state but then it keeps going through the search space.

Code :

```// check for goal state if( problem.isGoalState( node.getState() ) ) { System.out.println( "Yes"); return node; }```
Attachment 773
• October 1st, 2011, 01:41 PM
Zaxx81
Quote:

Originally Posted by dabdi
Did you try my suggestion ? It is pretty straight forward and I can not see why it will not work.
Declare a member variable goalFound.
Code java:

`Boolean goalFound;`
Set it to false initially (in constructor)
Code java:

`goalFound = false;`
Then wherever you test for termination (isGoalState(node)) , do the following instead
Code java:

```if(goalFound || problem.isGoalState( node.getState() ) ) { System.out.println( "Yes"); goalFound = true; return node; }```

How do I stop the for loop? Because even with goalFound, the other Successor nodes in the this will return themselves or null...
• October 1st, 2011, 01:51 PM
Sean4u
Returning something from a successful search method invocation seems like a good way of terminating your search. Can you continue / break your loop depending on the return value of the search method? Here's a little example that uses depth-limited recursion (hard-coded at 5) and a return value to determine when to give up searching:
Code java:

```package com.javaprogrammingforums.domyhomework;   import java.util.Scanner;   public class DepthLimitedSearch { private static final int DEPTH_LIMIT = 5; private static final char[] CHARS = "abcdefghijklmnopqrstuvwxyz".toCharArray(); public static void main(String[] args) { System.out.println("Enter a word to search for:"); String word = new Scanner(System.in).nextLine(); int effort = searchFor(word, 0); if (effort < 0) System.out.println("Couldn't find '" + word + "' after " + (-effort) + " attempts"); else System.out.println("Found! After " + effort + " attempts"); } private static int searchFor(String word, int index) { if (index > DEPTH_LIMIT) return -1; // not found int tries = 0; for (char c : CHARS) // 'search' for matching character at this depth { tries++; if (word.charAt(index) == c) { if (++index < word.length()) { int moreTries = searchFor(word, index); if (moreTries < 0) return moreTries - tries; return tries + moreTries; } else // found it return tries; } } return -tries; } }```
What principle of your problem makes the solution you seek more difficult than this?

edit: This isn't substantially different from dabdi's suggestion of a redundant flag with the right scope.
• October 1st, 2011, 01:56 PM
dabdi
Quote:

How do I stop the for loop? Because even with goalFound, the other Successor nodes in the this will return themselves or null...
You have isGoalState inside the for loop as well so make the same change.
Code java:

```// recursively expands search space output = recursiveExpandNode( current ); if( problem.isGoalState( current.getState() ) ) break;```
change the above to
Code java:

``` output = recursiveExpandNode( current ); if(goalFound || problem.isGoalState( current.getState() ) ) { goalFound = true; break; }```
This simple method is used even in threaded applications where many threads participate in finding one goal.
• October 1st, 2011, 02:20 PM
Sean4u
Quote:

That's your solution's natural ground, where it's behaving not only as a success flag but also as a communications channel. If the task in hand is 'can a matching item be found?', then a Boolean / boolean flag makes sense. If it's 'find the one-and-only matching item', then a reference (or AtomicReference) may make more sense. If it's possible that more than one solution exists, then threads can check a shared result list to see if it's not empty.

For the single threaded case, it ought to be possible to propagate 'success' back through the invocation chain, terminating each level as it goes, without the need for a shared variable.
• October 1st, 2011, 03:00 PM
dabdi
Quote:

Originally Posted by Sean4u
That's your solution's natural ground, where it's behaving not only as a success flag but also as a communications channel. If the task in hand is 'can a matching item be found?', then a Boolean / boolean flag makes sense. If it's 'find the one-and-only matching item', then a reference (or AtomicReference) may make more sense. If it's possible that more than one solution exists, then threads can check a shared result list to see if it's not empty.

For the single threaded case, it ought to be possible to propagate 'success' back through the invocation chain, terminating each level as it goes, without the need for a shared variable.

Yes proper back propagation is required for more complex goals. The OP's problem is very simple as to not require advanced solutions. He can even use a longjump once he encounters a goal at a leaf node but that is a very bad design. When the goal is not as clear cut, for example if it is finding shortest path, best action (i.e move in a zero-sum game etc), one would have to do proper back-propagation of updating the internal nodes. I am sure he will learn about those later. I still use volatile variables with atomic operations in my c++ projects for synchronization, to quit program on user interrupt, or when one of the worker threads find out work at the current node need to be stopped etc...
• October 1st, 2011, 03:19 PM
Zaxx81
Finally got it to work, with everyone's help. I ended up creating a class variable "Boolean goalFound" and "Successor goalNode". So once I find a goal node, I set goalFound to true and store it in goalNode. This ensured I only returned the first goal node. I still had the problem of the program continuing through the for loops of every recusive branch. So I added a check at the beggining of the for loop to see if goalFound was true, which instead of returning null like I thought, I used break on the for statement so it doesn't iterate any more for that branch.

The sad thing is this is 1 of my last two assignments for my Masters in Computer Science. What sucks is that I did Computer Engineering for my undergrad, so we didn't have any programming focused classes beyond data structures, just classes that we programmed in. Never had to do anything more complex with recursion than fibonnacci number.

Below is the final code for that class. Thanks again!

Code :

```public class DepthLimitedSearch extends AbstractSearch { int depthLimit; Boolean goalFound; Successor goalNode;   public DepthLimitedSearch(Problem p, int maxDepth) { super(p); this.depthLimit = maxDepth; this.goalFound = false; this.goalNode = null; } public Solution search() { // stores the solution to return Solution solution = null; Successor solutionNode = null;   solutionNode = recursiveExpandNode( (Successor)problem.getInitialState() );   if( this.goalNode != null ) solution = new Solution( this.goalNode, this.goalNode.getDepth() ); return solution; }   private Successor recursiveExpandNode( Successor node ) { Successor output = null;   // check for goal state if( !this.goalFound && problem.isGoalState( node.getState() ) ) { System.out.println( "Yes"); this.goalFound = true; this.goalNode = node; return node; }   // check for depth if( node.getDepth() > ( this.depthLimit - 1 ) ) return null;   List successorsList = problem.getSuccessorFunction().getSuccessors(node);   if( !successorsList.isEmpty() ) { for( Iterator itr = successorsList.iterator(); itr.hasNext(); itr.next() ) { if( this.goalFound ) break;   // get current Successor Successor current = (Successor)itr.getCurrent();   // set parent current.setParent( node );   // set depth current.setDepth(node.getDepth() + 1);   System.out.println( current.toString() );   // recursively expands search space output = recursiveExpandNode( current ); if( problem.isGoalState( current.getState() ) ) break; } } return output; } }```
• October 1st, 2011, 03:46 PM
Zaxx81
New code puzzle. The first time I run the program the menu of test cases print in the wrong order. When it loops back to give the user a chance to enter another case the menu order is correct. Can anyone see anything wrong in the attached code? Also attached a screenshot.

http://i54.tinypic.com/2882zjs.png

Code :

```package VacuumWorld.testing;   import java.io.BufferedReader; import java.io.InputStreamReader;   import VacuumWorld.Environment; import VacuumWorld.Location; import VacuumWorld.VacuumSearchAgent;   import dataStructures.HashMap; import dataStructures.Iterator;     /** * Class VacuumWorldDLSTester. * <p> * This class runs test cases for testing a depth-limited search for the * VacuumWorld problem. * <p> * Written by: Roger West * University of Illinois at Springfield * 01/2006 */ public class VacuumWorldDLSTester {   /************ * constants ***********/   /** indicates all available tests should be run in batch mode */ private final static String RUN_ALL_TESTS = "ALL";     /************* * attributes ************/   /** the collection of TestCase objects available for testing */ private HashMap testCases;     /*************** * constructors **************/   /** * Create a new VacuumWorldDLSTester with an empty collection of test cases. */ public VacuumWorldDLSTester() { // create HashMap for storing test cases testCases = new HashMap();     }     /********** * methods *********/   /** * Query user for depth limit to use for testing. */ private int queryDepth() { int depth = 0;   try { BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));   System.out.print("\nEnter depth limit for DepthLimitedSearch: ");   String input = bfr.readLine();   depth = Integer.parseInt(input); } catch (Exception e) { depth = 0; }   return depth; }     /** * Populate collection of test cases. Currently all test cases are hard- * coded inside this method. * * @param depth depth limit for testing the depth-limited search */ private void populateVacuumWorldDLSTestCases(int depth) { // test case object VacuumWorldDLSTestCase tc;   // test case id String id;   // test case description String description;   // the test case Environment test;   // test case expected result String expectedResult;   // Test Case #1: id = "1"; description = "D-" + depth + " LEFT (dirty) (vacuum agent present) | RIGHT (dirty)"; expectedResult = "Optimal solution: Suck --> Move Right --> Suck"; test = new Environment(); test.addLocation(Location.LEFT, new Location(Location.LEFT, true)); test.addLocation(Location.RIGHT, new Location(Location.RIGHT, true)); test.setVacuumAgentLocation(Location.LEFT); tc = new VacuumWorldDLSTestCase(id, description, test, depth, expectedResult); testCases.add(id, tc);   // Test Case #2: id = "2"; description = "D-" + depth + " LEFT (dirty) | RIGHT (dirty) (vacuum agent present)"; expectedResult = "Optimal solution: Suck --> Move Left --> Suck"; test = new Environment(); test.addLocation(Location.LEFT, new Location(Location.LEFT, true)); test.addLocation(Location.RIGHT, new Location(Location.RIGHT, true)); test.setVacuumAgentLocation(Location.RIGHT); tc = new VacuumWorldDLSTestCase(id, description, test, depth, expectedResult); testCases.add(id, tc);   // Test Case #3: id = "3"; description = "D-" + depth + " LEFT (clean) (vacuum agent present) | RIGHT (clean)"; expectedResult = "Optimal solution: Do nothing"; test = new Environment(); test.addLocation(Location.LEFT, new Location(Location.LEFT, false)); test.addLocation(Location.RIGHT, new Location(Location.RIGHT, false)); test.setVacuumAgentLocation(Location.LEFT); tc = new VacuumWorldDLSTestCase(id, description, test, depth, expectedResult); testCases.add(id, tc);   // Test Case #4: id = "4"; description = "D-" + depth + " LEFT (clean) | RIGHT (clean) (vacuum agent present)"; expectedResult = "Optimal solution: Do nothing"; test = new Environment(); test.addLocation(Location.LEFT, new Location(Location.LEFT, false)); test.addLocation(Location.RIGHT, new Location(Location.RIGHT, false)); test.setVacuumAgentLocation(Location.RIGHT); tc = new VacuumWorldDLSTestCase(id, description, test, depth, expectedResult); testCases.add(id, tc);   // Test Case #5: id = "5"; description = "D-" + depth + " LEFT (clean) (vacuum agent present) | RIGHT (dirty)"; expectedResult = "Optimal solution: Move Right --> Suck"; test = new Environment(); test.addLocation(Location.LEFT, new Location(Location.LEFT, false)); test.addLocation(Location.RIGHT, new Location(Location.RIGHT, true)); test.setVacuumAgentLocation(Location.LEFT); tc = new VacuumWorldDLSTestCase(id, description, test, depth, expectedResult); testCases.add(id, tc);   // Test Case #6: id = "6"; description = "D-" + depth + " LEFT (clean) | RIGHT (dirty) (vacuum agent present)"; expectedResult = "Optimal solution: Suck"; test = new Environment(); test.addLocation(Location.LEFT, new Location(Location.LEFT, false)); test.addLocation(Location.RIGHT, new Location(Location.RIGHT, true)); test.setVacuumAgentLocation(Location.RIGHT); tc = new VacuumWorldDLSTestCase(id, description, test, depth, expectedResult); testCases.add(id, tc);   // Test Case #7: id = "7"; description = "D-" + depth + " LEFT (dirty) (vacuum agent present) | RIGHT (clean)"; expectedResult = "Optimal solution: Suck"; test = new Environment(); test.addLocation(Location.LEFT, new Location(Location.LEFT, true)); test.addLocation(Location.RIGHT, new Location(Location.RIGHT, false)); test.setVacuumAgentLocation(Location.LEFT); tc = new VacuumWorldDLSTestCase(id, description, test, depth, expectedResult); testCases.add(id, tc);   // Test Case #8: id = "8"; description = "D-" + depth + " LEFT (dirty) | RIGHT (clean) (vacuum agent present)"; expectedResult = "Optimal solution: Move Left --> Suck"; test = new Environment(); test.addLocation(Location.LEFT, new Location(Location.LEFT, true)); test.addLocation(Location.RIGHT, new Location(Location.RIGHT, false)); test.setVacuumAgentLocation(Location.RIGHT); tc = new VacuumWorldDLSTestCase(id, description, test, depth, expectedResult); testCases.add(id, tc);   }     /** * Display menu of available test cases and allow user to choose test case * to run. */ public void test() { int maxDepth = queryDepth();   populateVacuumWorldDLSTestCases(maxDepth);   System.out.println("\nChoose a test case:"); for (Iterator itr = testCases.iterator(); itr.hasNext(); itr.next()) { VacuumWorldDLSTestCase tc = (VacuumWorldDLSTestCase)itr.getCurrent();   System.out.println( " " + tc.getID() + ": " + tc.getDescription()); } System.out.println();   try { BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in));   String testID = bfr.readLine();   testID.trim();   runTest(testID);   test(); } catch (Exception e) { e.printStackTrace(); }   }     /** * Execute the test case corresponding to the specified ID. * * @param id the unique identifier of the test case to run */ private void runTest(String id) { VacuumWorldDLSTestCase tc = (VacuumWorldDLSTestCase)testCases.get(id);   if (tc != null) { VacuumSearchAgent agent = tc.getAgent();   agent.solveProblem(); } else { System.out.println("Error - chosen ID does not match any existing test cases!"); } }     /** * Execute all test cases in batch mode. * * Currently not implemented. */ private void runAllTests() {   } }```
• October 1st, 2011, 04:04 PM
Sean4u
D'oh! duplicate post...
• October 1st, 2011, 04:07 PM
Sean4u
Uh? HashMap isn't in any way sorted, so the out-of-order is to be expected. Changing order is as weird as in-order. TreeMap would give you sorting, LinkedHashMap reliable ordering. Do you remove / put the values, perhaps with a change of data that would effect their hashCode()?
• October 1st, 2011, 04:27 PM
Zaxx81
Quote:

Originally Posted by Sean4u
Uh? HashMap isn't in any way sorted, so the out-of-order is to be expected. Changing order is as weird as in-order. TreeMap would give you sorting, LinkedHashMap reliable ordering. Do you remove / put the values, perhaps with a change of data that would effect their hashCode()?

That was instructor provided and it is in the correct order every time it loops back. I can live with it for a HW assignment, but it just kind of bugs me.
• October 1st, 2011, 04:35 PM
dabdi
Quote:

Originally Posted by Zaxx81
New code puzzle. The first time I run the program the menu of test cases print in the wrong order. When it loops back to give the user a chance to enter another case the menu order is correct. Can anyone see anything wrong in the attached code? Also attached a screenshot.

As sean4u pointed out hashmap uses hash tables i.e (key,value) pair, so it is not sorted in any way. Interestingly it seems it is non-deterministic as well (you get different sequence every time you run the program). This is bad for debugging. I suspect it is because different set of hash keys (random numbers) are generated every time. May be there is a way to set the random number seed to a constant value.
More here is the Java HashMap keySet() iteration order consistent? - Stack Overflow
• October 1st, 2011, 04:55 PM
Sean4u
You should use LinkedHashMap or TreeMap if you care about the order of your iterators. I'm agog at the order *changing* though - I'd be interested to see an SSCCE that demonstrated that behaviour. I can't help thinking the 'ordered' result is pure luck or perhaps a bad hashCode() implementation.
• October 1st, 2011, 05:05 PM
Sean4u
Waidaminnit! Since when did HashMap have an iterator() method?
Quote:

import dataStructures.HashMap
Quote:

That was instructor provided
:facepalm:
• October 1st, 2011, 07:20 PM
Zaxx81