;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; This file contains functions to create and run randomized experiments for the ; multi-agent world. See header comments of the functions for detailed information. ; 10/13/2012: Authored by Daphne Liu. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ;To run multiple experiments, run the following commands. ;(load "compile-all") ;(load "multirun") ;(runRandomized numAgents width numBlockedPts n-steps-per-agent &OPTIONAL (cut-off-seconds 100.0)) ;e.g., (runRandomized 4 6 10 80) (defparameter *n-agents* 0) (defparameter *agent-array* 'NIL) (defparameter *agent-positions* 'NIL) (defparameter *goals* 'NIL) (defparameter *agent-goal-indices* 'NIL) (defparameter *blocked-points* 'NIL) (defparameter *point-array* 'NIL) (defparameter *length-valid-point-array* 0) (defparameter *agent-cpuruntimes* 'NIL) ; MUST USE INTERN INSTEAD OF MAKE-SYMBOL for LISP's set operations to work. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; This function initializes *point-array* to an array of (Arg size) points of the form ; p11, p12, ..., etc. corresponding to points in the gridworld of dimensions ; (Arg width by Arg width), and initializes *length-valid-point-array* to (Arg size). ; This function returns a list consisting of points and roads abiding by the syntax of ; the actual arguments needed by function (def-roadmap points roads). ; 10/13/2012: Created by Daphne Liu. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (defun createRandomizedMap (width size) (let (points roads (hor-tens 0) ver-road-lst ver-pt road-lst pt pt-integer ver-pt-integer) (loop for i from 1 to width do (incf hor-tens 10) (loop for j from width downto 1 do (setq pt-integer (+ hor-tens j)) (setq pt (intern (concatenate 'string "p" (write-to-string pt-integer)))) (setq ver-pt-integer (+ (* j 10) i)) (setq ver-pt (intern (concatenate 'string "p" (write-to-string ver-pt-integer)))) (push pt points) (when (< j width) (push 1 road-lst) (push 1 ver-road-lst) ) (push pt road-lst) (push ver-pt ver-road-lst) );end of j loop (push (intern (concatenate 'string "hor" (write-to-string i))) road-lst) (push road-lst roads) (setq road-lst 'NIL) (push (intern (concatenate 'string "ver" (write-to-string i))) ver-road-lst) (push ver-road-lst roads) (setq ver-road-lst 'NIL) );end of i loop (setq *point-array* (make-array size :INITIAL-CONTENTS points)) (setq *length-valid-point-array* size) ;(format t "~% points ~A ~%" points) ;(format t "~% roads ~A ~%" roads) ;(format t "~% (def-roadmap ~% ~a ~% ~a )~%" points roads) ;(def-roadmap points roads) (list points roads) ) ) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; Note that prior to calling this function *point-array* and *length-valid-point-array* ; must have been set. This function randomly generates (Arg howManyToCreate) points of ; the gridworld and returns these randomly generated points in a list. (Boolean Arg ; throwAway) indicates whether or not an already randonly generated point should be ; removed from consideration in subsequent or successive random generations of points. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (defun createRandomizedPtList (howManyToCreate &OPTIONAL (throwAway 'T)) (let (result-lst pt index) (dotimes (i howManyToCreate) (setq index (random *length-valid-point-array*)) (setq pt (aref *point-array* index)) (when (eq throwAway 'T) (decf *length-valid-point-array* 1) (setf (aref *point-array* index) (aref *point-array* *length-valid-point-array*)) (setf (aref *point-array* *length-valid-point-array*) pt) ) (push pt result-lst) ) result-lst ) ) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; (def-roadmap points roads) must have been called before this function since this ; function uses the 'next property information attached to each point to ascertain ; connectivity between each agent's and its goal. Similarly, *agent-positions*, *goals* ; and *n-agents* must have been set. A point's 'next property is a list consisting of ; lists of the form (road neighbor_point distance_to_this_neighbor_point_along_road) . ; This function randomly generates (Arg howManyToCreate) blocked points for the gridworld, ; gridworld, sets *blocked-points* to these points, and adds that each of these blocked ; points is occupied to *protected-facts* and *world-facts*. (Boolean Arg throwAway) ; indicates whether or not an already randonly generated point should be removed from ; consideration in subsequent or successive random generations of points. ; 10/13/2012: Created by Daphne Liu. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (defun createRandomizedBlockedPoints (howManyToCreate &OPTIONAL (throwAway 'T)) (let (currPt goalPt visited-pts neighborPts ptQueue (numSuccesses 0) (numBlockedPtSetsTried 0) lst-pairs-begin-end ) (dotimes (i *n-agents*) (push (list (aref *agent-positions* i) (aref *goals* i)) lst-pairs-begin-end) ) ;;Keep randomly generating the set of blocked points until we are sure that ;;given the set of blocked points, each agent can in principle reach its ;;goal position from its initial position. (LOOP WHILE (< numSuccesses *n-agents*) DO (incf numBlockedPtSetsTried 1) (when (AND (> numBlockedPtSetsTried 1) (eq throwAway 'T)) (incf *length-valid-point-array* howManyToCreate) ) (setq *blocked-points* (createRandomizedPtList howManyToCreate throwAway)) (setq numSuccesses 0) (dolist (pair lst-pairs-begin-end) (setq visited-pts *blocked-points*) (setq goalPt (second pair)) (setq ptQueue (list (first pair))) (LOOP WHILE (NOT (NULL ptQueue)) DO (setq currPt (pop ptQueue)) (push currPt visited-pts) ;e.g., (set-differencef '(a b c a) '(a b d)) yields (C) (setq neighborPts (set-differencef (mapcar #'second (get currPt 'next)) visited-pts)) ; By using set-differencef, we ensure that neighborPts contains no duplicates. (when (member goalPt neighborPts) (return (incf numSuccesses 1)) ) ; Note at this point, neighborPts already contains only non-duplicates and points ; not already appearing in visited-pts. (setq ptQueue (append ptQueue neighborPts)) ) ) ) ;Daphne: Moved 10/13/2012 from (def-roadmap ...) in gridworld-definitions.lisp ;to work with multiruns where randomly generated *blocked-points* are ;instituted if and only if they allow for connectivity between each agent ;to its goal. (dolist (p *blocked-points*) (add_tuple_to_hashtable (list 'is_occupied p) *protected-facts* nil) (add_tuple_to_hashtable (list 'is_occupied p) *world-facts* nil) ) ;(format t "~% ~a *blocked-points* ~a ~%" numBlockedPtSetsTried *blocked-points*) ) ) ;(defun createRandomizedPtList (width totalSize howManyToCreate) ; (let (result-lst num quotient remainder) ; (dotimes (i howManyToCreate) ; (setq num (random totalSize)) ; (setq quotient (floor (/ num width))) ; (setq remainder (mod num width)) ; (push (intern (concatenate 'string "p" (write-to-string (+ 11 (* 10 quotient) remainder)))) result-lst) ; ) ; result-lst ; ) ;) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; I copied this function from the http://cl-cookbook.sourceforge.net/dates_and_times.html ; This function computes the real time and the CPU run time taken to execute ; (Arg &body forms). The function prints the resulting times and returns a list composed ; of (a) the real time (in seconds)and (b) the CPU run time (in seconds) taken. ; From the URL, ``There are actually two different internal time clocks in Lisp: one of ; them meaures the passage of "real" time (the same time that universal time measures, ; but in different units), and the other one measures the passage of CPU time, that is, ; the time your CPU spends doing actual computation for the current Lisp process. On most ; modern computers these two times will be different, since your CPU will never be ; entirely dedicated to your program (even on single-user machines, the CPU has to devote ; part of its time to processing interrupts, performing I/O, etc).'' ; Therefore, it seems that only (b) and the runtimes and their average that ; (runrandomized ...) will output to the file ***_***CPUTIMES.txt are of interest to ; our timing purposes. ; 10/13/2012: Created by Daphne Liu. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (defmacro timing (&body forms) (let ((real1 (gensym)) (real2 (gensym)) (run1 (gensym)) (run2 (gensym)) (result (gensym)) realTimeResult runTimeResult) `(let* ((,real1 (get-internal-real-time)) (,run1 (get-internal-run-time)) (,result (progn ,@forms)) (,run2 (get-internal-run-time)) (,real2 (get-internal-real-time))) (setq realTimeResult (/ (- ,real2 ,real1) (+ internal-time-units-per-second 0.00))) (setq runTimeResult (/ (- ,run2 ,run1) (+ internal-time-units-per-second 0.00))) ;(format *debug-io* "~%;;; Computation took:~%") ;(format *debug-io* ";;; ~f seconds of real time~%" realTimeResult) ;(format t ";;; ~f seconds of run time~%" runTimeResult) ;,result ;the original result returned (list realTimeResult runTimeResult) ) ) ) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; This function invokes (notice-new-local-facts ...) and (go! ...) for the agent indexed ; (Arg j) with name (Arg agent). This is separated out from function ; (runMultipleStepsPerAgent ...) only for the purpose of timing. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (defun noticeGoforAgent (j agent) ; First update the agent's knowledge, since there may ; have been local changes cuased by other agents; then go!. (notice-new-local-facts (aref *curr-state-node* j) agent) (go! j); This resets the jth agent's current knowledge state; ; naturally, the actual world is altered as well ; and the next agent will act therein. ) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; This function invokes (notice-new-local-facts ...) and (go! ...) for each of the ; *n-agents* agents (Arg n-steps-per-agent) times consecutively, until the agent reaches ; its goal or until the agent has met the (Arg cut-off-seconds) limit, whichever comes ; first. This function returns a list composed of a list ; (numSuccessfullyAccomplishedAgents, totalCPURunTime, and totalNumIters), followed by ; list tuples of the form ; (successful agent's name, said agent's cpu run time, # of (noticeGoforAgent ...)s ; invoked on said agent) for these agents in an anti-chronological order. ; 10/18/2012: Updated by Daphne Liu. ; 10/13/2012: Created by Daphne Liu. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (defun runMultipleStepsPerAgent (n-steps-per-agent &OPTIONAL (cut-off-seconds 100.0)) (let (agent loc realtime-runtime-lst (numFinished 0) (finishedAgents 'NIL) (numCanReturn 0) (canReturnAgents 'NIL) (totalRunTime 0.00) (numPerformedIters 0) ) ; Initialize / reset the cpu runtimes for each agent. ; We can also put the code for initialization / resetting into the calling function if ; counting the run time of this entire current function without wanting to count in ; the time for initialization / resetting. (setq *agent-cpuruntimes* (make-array *n-agents* :INITIAL-ELEMENT 0.00)) (dotimes (i n-steps-per-agent); i = step index (dotimes (j *n-agents*) ; j = agent index (when (not (member j canReturnAgents)); ignore finished agents (setq agent (aref *agent-array* j)) ; Invoke notice-local-facts and go! and tally up the cpu run time for agent indexed j. (setq realtime-runtime-lst (timing (noticeGoforAgent j agent))) (incf numPerformedIters 1) (incf totalRunTime (second realtime-runtime-lst)) (incf (aref *agent-cpuruntimes* j) (second realtime-runtime-lst)) (setq loc (find-location agent (state-node-wff-htable (aref *curr-state-node* j)))) ; If the agent is at its goal, put it on the finishedAgents list. (if (eql loc (aref *goals* j)) (progn ;(format t "~%~%==> AGENT ~s HAS REACHED ITS GOAL ~s !" agent loc) ;Add (agent, agent's cpu runtime, # of (noticeGoforAgent ...)s invoked on agent) to the result list. (push (list agent (aref *agent-cpuruntimes* j) numPerformedIters) finishedAgents) (incf numFinished 1) (incf numCanReturn 1) (push j canReturnAgents) ;Return from this function earlier if all *n-agents* are finished before loop ends. (when (eq numCanReturn *n-agents*) (push (list numFinished totalRunTime numPerformedIters) finishedAgents) (return-from runMultipleStepsPerAgent finishedAgents) ) ) ; Check if unfinished agent has exceeded the cut-off time. (when (> (aref *agent-cpuruntimes* j) cut-off-seconds) (incf numCanReturn 1) (push j canReturnAgents) ;Return from this function earlier if all *n-agents* can return before loop ends. (when (eq numCanReturn *n-agents*) (push (list numFinished totalRunTime numPerformedIters) finishedAgents) (return-from runMultipleStepsPerAgent finishedAgents) ) ) ) ); end of 'when' for active agents ); end of agent loop ); end of step loop (push (list numFinished totalRunTime numPerformedIters) finishedAgents) finishedAgents ) ) ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ; This function creates and runs randomized experiments for (Arg numAgents) agents ; in a gridworld of dimensions (Arg width x Arg width), with (Arg numBlockedPts) blocked ; points, invoking (notice-new-local-facts ...) and (go! ...) on each agent for at most ; (Arg n-steps-per-agent) times (or earlier - until the agent reaches its goal position). ; Optional (Arg cut-off-seconds) specifies the # of seconds for cut-off-limit; for more ; details, read the header comment of function (runMultipleStepsPerAgent ...). ; The function displays output to files of the names OUTa_b_c_d_i.txt, where a-d are ; integers specified by the 4 Args and i (e.g., 0, 1, 2, etc.) indicates the sequential ; order of the file in the set of output files matching the config params a-d. The real ; times (in seconds) of these experiments and their avg (last line of the output file, ; also in seconds) are output to the file of the name OUTa_b_c_d_REALTIMES.txt. The CPU ; run times (in seconds) of these experiments and their avg (last line of the output ; file, also in seconds) are output to the file of the name OUTa_b_c_d_CPUTIMES.txt. ; ; As per the URL http://cl-cookbook.sourceforge.net/dates_and_times.html ; ``There are actually two different internal time clocks in Lisp: one of them measures ; the passage of "real" time (the same time that universal time measures, but in different ; units), and the other one measures the passage of CPU time, that is, the time your CPU ; spends doing actual computation for the current Lisp process. On most ; modern computers these two times will be different, since your CPU will never be ; entirely dedicated to your program (even on single-user machines, the CPU has to devote ; part of its time to processing interrupts, performing I/O, etc).'' ; Therefore, it seems that only (b) and the CPU run times and their average that ; (runrandomized ...) will output to the file ***_CPUTIMES.txt are of interest to our ; timing purposes. ; 10/16/2012: Updated by Daphne Liu to output to file ***_sucCPUTIMES.txt and ; ***_allCPUTIMES.txt instead, where the former is to store the CPU run times of ; successfully finished agents and their avg CPU run time (the last line), and the ; latter is to store the CPU run times of all - finished or not - agents and their ; avg CPU run time (the last line). ; 10/13/2012: Created by Daphne Liu. ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; (defun runRandomized (numAgents width numBlockedPts n-steps-per-agent &OPTIONAL (cut-off-seconds 100.0)) (let* (start-time end-time elapsed-time finishedAgents ;dribbleFileName ;Variable howManyTimesToRepeat denotes the number of randomized experiments ;with the given settings (numAgents width numBlockedPts n-steps-per-agent &OPTIONAL (cut-off-seconds 100.0)) ;to create and run, in order to take the average of their runtimes. (howManyTimesToRepeat 50) ;(total-realtime 0.00) (total-runtime 0.00) (size (* width width)) (startOutfileName (concatenate 'string "OUT" (write-to-string numAgents) "_" (write-to-string width) "_" (write-to-string numBlockedPts) "_" (write-to-string n-steps-per-agent))) (successruntimeFileName (concatenate 'string startOutfileName "_sucCPUTIMES.txt")) (totalCPURunTime 0.00) (totalNumIters 0) (pt-road-lst (createRandomizedMap width size)) (currMaxCPURunTime 0) (currMaxIters 0) (currMinCPURunTime (* numAgents cut-off-seconds)) (currMinIters (* numAgents n-steps-per-agent)) numSuccesses cpuRunTime numIters ) (setq *n-agents* numAgents) ;MUST LOAD THESE FILES HERE SINCE THEY INITIALIZE ARRAYS of SIZE *n-agents*. (load "gridworld-definitions") (load "gridworld-planning") (load "simulation-and-function-evaluation") (load "go.lisp"); uncompiled -- to avoid compiler bugs (load "implement-effects.lisp"); uncompiled -- to avoid compiler bugs ;It's fine to load the world just once since (place-object ...) and ;(def-roadmap ...) have been moved from the world to this file. (load "gridworld-world") (setq *agent-array* (make-array *n-agents* :initial-contents (butlast *agent-names* (- 10 *n-agents*)))) (dotimes (ttemp1 howManyTimesToRepeat); START OF ttemp1 LOOP ;;Make sure to remove the things below from the world file ;;and place them below instead to randomize. ;(setq dribbleFileName (concatenate 'string startOutfileName "_" (write-to-string ttemp1) ".txt")) ;(dribble dribbleFileName) ; Create the roadmap gridworld. (setq *length-valid-point-array* size) (apply #'def-roadmap pt-road-lst) ;Invoke def-roadmap on the list of points and roads (setq *agent-positions* (make-array *n-agents* :initial-contents (createRandomizedPtList *n-agents*) )); Create randomized initial positions ;(format t "~% *agent-positions* ~a ~%" *agent-positions*) (setq *goals* (make-array *n-agents* :initial-contents (createRandomizedPtList *n-agents*) )); Create randomized goal positions ;(format t "~% *goals* ~a ~%" *goals*) (createRandomizedBlockedPoints numBlockedPts) (setq *agent-goal-indices*; allows hash access to indices, and (make-hash-table :size 23)) (dotimes (j *n-agents*) (setf (gethash (aref *agent-array* j) *agent-goal-indices*) j) ;from an agent name to the agent's index (setf (gethash (aref *goals* j) *agent-goal-indices*) j)) ;from a goal index to the corresponding agent's index ; place-object has been altered so as to add 'is-occupied' facts ; (for agents placed at a point) to *world-facts* and *protected-facts*. (dotimes (j *n-agents*) (place-object (aref *agent-array* j) 'agent (aref *agent-positions* j) 0 nil nil nil) ) ; Initialize the *curr-state-node* of each agent. (dotimes (j *n-agents*) (initialize-state-node j) ) (setq finishedAgents (runMultipleStepsPerAgent n-steps-per-agent cut-off-seconds)) ;The first element of the result lst finishedAgents is a list of the form ;(numSuccessfullyAccomplishedAgents, totalCPURunTime, and totalNumIters). ;All its other elements are each a list of the form ;(successful agent's name, said agent's cpu run time, # of (noticeGoforAgent ...)s ; ;invoked on said agent). (setq numSuccesses (first (first finishedAgents))) (if (= numSuccesses *n-agents*) (progn (setq cpuRunTime (second (first finishedAgents))) (setq numIters (third (first finishedAgents))) (when (< currMaxCPURunTime cpuRunTime ) (setq currMaxCPURunTime cpuRunTime ) ) (when (< currMaxIters numIters) (setq currMaxIters numIters) ) (when (> currMinIters numIters) (setq currMinIters numIters) ) (when (> currMinCPURunTime cpuRunTime) (setq currMinCPURunTime cpuRunTime) ) (incf totalCPURunTime cpuRunTime) (incf totalNumIters numIters) ) (decf ttemp1 1);Do another run since the current run is not a successful one. ) ;(dribble) (with-open-file (outfile successruntimeFileName :direction :output :if-exists :append :if-does-not-exist :create) (print (first finishedAgents) outfile) ) ); END of ttemp1 LOOP ; Output the average CPU run time and average number of iterations to file. (with-open-file (outfile successruntimeFileName :direction :output :if-exists :append :if-does-not-exist :create) ; Output the average CPU run time and average number of iterations to file. (print (/ totalCPURunTime howManyTimesToRepeat) outfile) (print (/ totalNumIters (+ howManyTimesToRepeat 0.0)) outfile) ; Output the maximum CPU run time and maximum number of iterations to file. (print (list currMinCPURunTime currMaxCPURunTime) outfile) (print (list currMinIters currMaxIters) outfile) ) ) )