%latex diplom_main.tex
%bibtex diplom_main

\documentclass[11pt,a4paper,footinclude,headinclude,pagesize]{article}%article;report;book;scrbook
\usepackage{ngerman} % Silbentrennung nach neuer Rechtschreibung
\usepackage[T1]{fontenc} % Type 1 Schriften
\usepackage{times} % Da die Standard-LaTeX-Schrift bei mir mit Acrobat nicht funkt.
\usepackage[ansinew]{inputenc} % Verwendung von Umlauten
\usepackage{scrpage2} % Seitenformat
\usepackage{titletoc}
\usepackage{titlesec}
\usepackage{listings} % Programm-Listing
%\usepackage [usetoc]{titleref}
\usepackage{graphicx} % Einbindung von Graphiken
\usepackage{url} % URLs durch \url{}
\usepackage{bibgerm} % deutsche Bibliographie
\usepackage{txfonts}%Paket für das nat Symbol
%\usepackage{endfloat}%Paket für mehrere Gleitkommaobjekte auf einer Seite


% nächste vier Zeilen: Format des Inhaltsverzeichnisses
%\titlespacing{\section}{0pt}{5cm}{5cm}%spacing by sections {in front}{above}{below}
%\dottedcontents{section}[1.5em]{\addvspace{1.0em}}{1.3em}{0.7pc}
%\dottedcontents{subsection}[3.8em]{}{2.2em}{0.7pc}
%\dottedcontents{subsubsection}[7.0em]{}{3.1em}{0.7pc}

\setcounter{secnumdepth}{3}%%nummerierung der Unterabschnitte bis Tiefe

%\renewcommand{\efloatseparator}{\mbox{}}%%mehrere Gleitobjekte auf einer Seite
\setcounter{topnumber}{4}%%maximale Gleitobjekte oben auf einer Seite
\setcounter{bottomnumber}{4}%%maximale Gleitobjekte unten auf einer Seite
\setcounter{totalnumber}{6}%%maximale Gleitobjekte auf einer Seite
\renewcommand{\textfraction}{0.05}%%Anteil einer Seite der mindestens für Text reserviert ist

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Definitionen für das Verwenden von Listings

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Beginn des Dokuments


\begin{document}

\ihead{\slshape \headmark } % Darstellung von Sectionnummer und -name
\ohead{}
\chead{}
\pagenumbering {arabic}

\title{Racing robots Problem}
\author{Bernd Österholz}
\date{28.08.2005}

\maketitle

\section{Racing robots}

\label{racingR}

%racing robots link (???)

Das racing robots Problem ist ein Planungsproblem. Dabei besteht die Welt aus einen quadratischen Grundplan mit einer festen Anzahl von quadratischen Feldern (ähnlich einem Schachbrett), die horizontal und vertikal angeordnet sind, zwischen denen sich Wände befinden können. Auf diesen Feldern können Roboter stehen, die jeweils in horizontal und vertikal Richtungen bewegt werden können. Dabei bewegen sich die Roboter solange, bis sie gegen eine Wand oder den Grundplanrand stoßen. Eine Aktion besteht damit aus einem Roboter und einer der vier Richtungen, in die er bewegt wird. Weiterhin kann nur jeweils ein Roboter zu einer Zeit in Bewegung sein. Die maximale Anzahl der zur Verfügung stehenden Zeitschritte ist fest und in jedem Schritt muss ein Roboter bewegt werden. Ziel ist es, dass ein Roboter am Ende des letzten Zeitschrittes auf einem bestimmten Feld steht. Aufgabe des Planers ist es einen Plan dafür zu entwerfen.

Auch die Antwortmengenprogramme zur Berechnung des racing robots Problems bestehen aus zwei Teilen. Einen Teil zur Berechnung des Plans und einen Teil der die Welt darstellt (Datenteil).

Die Parameter für die Generierung der Welt, sind die Ausdehnung des Grundplans (die Felder neben- oder übereinander), die Anzahl der Wände, Roboter und maximalen Zeitschritte. Die Wände und Roboter werden dann an zufälligen Positionen auf dem Grundplan platziert.

Der Teil zur Berechnung des Plans wurde von mir im Rahmen einer Vorlesung zur Einführung in die Antwortmengenprogrammierung angefertigt. Damit stellt er eher ein Antwortmengenprogramm von einem Normalbenutzer dar, anstatt ein von Antwortmengenexperten optimiertes Antwortmengenprogramm, wie das weiter oben beschriebene zur Berechnung von hamiltonsche Zyklen.

\section{Quellcode}

Im Nachfolgendem ist der racing robots Quellcode angegeben.

\begin{lstlisting}[language=Prolog, numbers=left, frame=single, caption={Hämiltonsche Zyklen auf Randomisierte Graphen}, label={racingRGr},breaklines,xleftmargin=15pt,captionpos=b]
%Robot plan creator
%lparse -cn=k feld.lp rr.lp | smodels > answers.txt

%domains
#domain time(T),fild(X),fild(Y),fild(X1),fild(Y1),fild(X2),fild(Y2),robot(R),robot(R1).
%hide
#hide isBlockedR(R,X,Y,X1,Y1,T),free(R,X,Y,X1,Y1,T),fild(X),time(T),robot(R),blocked(X,Y,X1,Y1).

%generator

%generate all posible moves(inclusiv stop) of the robots
%yust one move per robot and time is posible
%the robots move from time t to t+1 so the last posible state time can't be
%the beginning time of the robot(that is wy "time(T+1)")
1{stop(R,T),up(R,T),down(R,T),left(R,T),right(R,T)}1:-time(T+1).

%generates wher the robot is in the next state if a move happens
%move up in X direction
isAt(R,X1,Y,T+1):-isAt(R,X,Y,T),isBlockedR(R,X1-1,Y,X1,Y,T),X1<X,free(R,X1,Y,X,Y,T),up(R,T).
%move down in X direction
isAt(R,X1,Y,T+1):-isAt(R,X,Y,T),isBlockedR(R,X1,Y,X1+1,Y,T),X1>X,free(R,X,Y,X1,Y,T),down(R,T).
%move left in Y direction
isAt(R,X,Y1,T+1):-isAt(R,X,Y,T),isBlockedR(R,X,Y1-1,X,Y1,T),Y1<Y,free(R,X,Y1,X,Y,T),left(R,T).
%move right in Y direction
isAt(R,X,Y1,T+1):-isAt(R,X,Y,T),isBlockedR(R,X,Y1,X,Y1+1,T),Y1>Y,free(R,X,Y,X,Y1,T),right(R,T).
%robot don't move
isAt(R,X,Y,T+1):-isAt(R,X,Y,T),stop(R,T).

%wher is something blocked for the Robot R at time T
%all borders round the robot are blocked
isBlockedR(R,X-1,Y,X,Y,T):-isAt(R1,X,Y,T),R!=R1. %left border
isBlockedR(R,X,Y-1,X,Y,T):-isAt(R1,X,Y,T),R!=R1. %uper border
isBlockedR(R,X,Y,X+1,Y,T):-isAt(R1,X,Y,T),R!=R1. %rigth border
isBlockedR(R,X,Y,X,Y+1,T):-isAt(R1,X,Y,T),R!=R1. %down border

%blocked edges of the great fild
isBlockedR(R,0,Y,1,Y,T). %left edge
isBlockedR(R,X,0,X,1,T). %upper edge
isBlockedR(R,X,Y,X+1,Y,T):-not fild(X+1). %rigth edge
isBlockedR(R,X,Y,X,Y+1,T):-not fild(Y+1). %down edge

%blocked is for the non moveable objects
%wher a non moveable block stands the border of the place is blocked for all time
isBlockedR(R,X3,Y3,X4,Y4,T):-blocked(X3,Y3,X4,Y4).

%free is for the straight lines the robot can move
%a robot can move from a fild to a fild if betwean them is not blocked
free(R,X,Y,X+1,Y,T):-not isBlockedR(R,X,Y,X+1,Y,T),fild(X+1). %moving up and down one place
free(R,X1,Y,X2,Y,T):-X1<X2,not isBlockedR(R,X1,Y,X1+1,Y,T),free(R,X1+1,Y,X2,Y,T). %moving up and down more place
free(R,X,Y,X,Y+1,T):-not isBlockedR(R,X,Y,X,Y+1,T),fild(Y+1). %moving right and left one place
free(R,X,Y1,X,Y2,T):-Y1<Y2,not isBlockedR(R,X,Y1,X,Y1+1,T),free(R,X,Y1+1,X,Y2,T). %moving right and left more place

%cutter
%no robots move at the same time
:-not stop(R1,T),not stop(R2,T),robot(R2),R1!=R2,time(T+1).
\end{lstlisting}

Im Datenteil wird mit \texttt{fild(1..n).} die Größe des Feldes definiert, wobei \texttt{n} die größe des Feldes ist
Die Anzahl \texttt{n} der Maximalen Schritte wird mit \texttt{time(0..n).} festgelegt.
Mit \texttt{blocked(X1,Y1,W2,Y2).} wird eine Wand zwischen dem Feld 1 Feldern mit x Position \texttt{X1} und y Position \texttt{Y1} und Feld 2 mit x Position \texttt{X2} und y Position \texttt{Y2} gestellt.
Roboter werden mit \texttt{robot(R).} erstellt und mit \texttt{isAt(R,X,Y,T).} plaziert, wobei \texttt{R} der Name für den Roboters ist, \texttt{X} die x Position und \texttt{Y} y Position der Feldes, auf dem er platziert wird, ist, und \texttt{Z} die Zeit zu der er Platziert wird ist.
Über den \texttt{compute} Teil kann dann mit \texttt{isAt(R,X,Y,T).} Fakt, die Zielbedinngung für die Roboter festgelgt werden.

\end{document}
