반응형

난이도 : 초급

McCoy David, Writer, Independent

2007 년 4 월 17 일

코너에 갇히거나 원하는 이동 방향에서 너무 많이 벗어나지 않으면서, 로봇과 벽 사이의 간격을 유지하는 알고리즘은 간단히 만들 수 없는 것 같습니다. 한 가지 간단한 솔루션으로, Factored wall avoidance가 있습니다. 이 글에서, David McCoy가 이를 구현하는 방법을 설명합니다.

With a few additions to the bot we built in "상대편의 움직임 추적하기"에서 구현했던 로봇에 몇 가지를 더 추가하여, 기존의 움직임 알고리즘 또는 문제가 많은 움직임 알고리즘에 Factored Wall Avoidance를 추가할 수 있다. Factored Wall Avoidance는 자신의 로봇과 벽의 근접성에 따라서 안전한 방향 설정(heading)으로 원하는 방향을 팩토링 함으로써 최상의 방향을 찾는 것이다.

일반 수학적 계산에 헬퍼 메소드 추가하기

우선 자주 사용되는 수학적 알고리즘에 헬퍼 메소드를 로봇에 추가한다.

calculateBearingToXYRadians() 메소드는 java.lang.Math 메소드 atan2()를 사용하여 sourceX,sourceY에서 targetX,targetY까지 절대 위치(absolute bearing)를 계산한 다음, 이 값을 sourceHeading에 관련된 위치로 변환한다.

그리고 normalizeAbsoluteAngleRadians() 메소드와 normalizeRelativeAngleRadians() 메소드도 필요하다.


Listing 1. 수학 헬퍼 메소드
                

private static final double DOUBLE_PI = (Math.PI * 2);
private static final double HALF_PI = (Math.PI / 2);

public double calculateBearingToXYRadians(double sourceX, double sourceY,
    double sourceHeading, double targetX, double targetY) {
        return normalizeRelativeAngleRadians(
           Math.atan2((targetX - sourceX), (targetY - sourceY)) -
               sourceHeading);
    }

public double normalizeAbsoluteAngleRadians(double angle) {
   if (angle < 0) {
        return (DOUBLE_PI + (angle % DOUBLE_PI));
    } else {
        return (angle % DOUBLE_PI);
    }
}

public static double normalizeRelativeAngleRadians(double angle) {
    double trimmedAngle = (angle % DOUBLE_PI);
    if (trimmedAngle > Math.PI) {
        return -(Math.PI - (trimmedAngle % Math.PI));
    } else if (trimmedAngle < -Math.PI) {
        return (Math.PI + (trimmedAngle % Math.PI));
    } else {
        return trimmedAngle;
    }
}




위로


AdvancedRobot을 back-as-front 기능으로 확장하기

다음으로, 로봇을 반대로 이동시키기 위한 back-as-front 기능을 제공하기 위해 AdvancedRobot 클래스 기능을 몇 가지 헬퍼 메소드로 확장할 필요가 있다.

  • getRelativeHeading() 메소드는 로봇의 현재 위치와 관련하여 정확한 방향을 계산한다.

  • reverseDirection() 메소드는 매우 단순하다. direction 인스턴스 변수를 토글링(toggle) 하고 로봇의 방향을 바꾼다. 감속할 때에는 시간이 걸리기 때문에 로봇은 속도에 따라서, 방향을 바꾸기 전에 최대 네 개의 프레임까지 같은 방향으로 움직일 수도 있다.

  • setAhead()setBack() 메소드는 AdvancedRobot 클래스에서 같은 이름의 메소드를 오버라이드 한다. 현재 방향에 대한 로봇의 속도를 설정하고, direction 인스턴스 변수를 필요에 따라 조정한다. 비례 연산은 로봇이 현재 움직이고 있는 방향과 관련이 있다.

  • setTurnLeftRadiansOptimal()setTurnRightRadiansOptimal() 메소드는 (Math.PI / 2) 보다 크게 회전하여 로봇의 방향을 바꾼다. adjustHeadingForWalls 메소드를 사용할 때 이러한 메소드들을 사용해야 하는데, 나중에 설명하겠다.

주: getter와 setter 메소드를 사용하는 대신 direction 인스턴스 변수에 직접 액세스 한다. 이것은 좋은 방법은 아니지만, 나는 내 로봇 코드에 이를 수행하여 데이터 액세스 속도를 높이곤 한다.


Listing 2. 로봇 헬퍼 메소드
                


public double getRelativeHeadingRadians() {
    double relativeHeading = getHeadingRadians();
    if (direction < 1) {
        relativeHeading =
                normalizeAbsoluteAngleRadians(relativeHeading + Math.PI);
    }
    return relativeHeading;
}

public void reverseDirection() {
    double distance = (getDistanceRemaining() * direction);
    direction *= -1;
    setAhead(distance);
}

public void setAhead(double distance) {
    double relativeDistance = (distance * direction);
    super.setAhead(relativeDistance);
    if (distance < 0) {
        direction *= -1;
    }
}

public void setBack(double distance) {
    double relativeDistance = (distance * direction);
    super.setBack(relativeDistance);
    if (distance > 0) {
        direction *= -1;
    }
}

public void setTurnLeftRadiansOptimal(double angle) {
    double turn = normalizeRelativeAngleRadians(angle);
    if (Math.abs(turn) > HALF_PI) {
        reverseDirection();
        if (turn < 0) {
            turn = (HALF_PI + (turn % HALF_PI));
        } else if (turn > 0) {
            turn = -(HALF_PI - (turn % HALF_PI));
        }
    }
    setTurnLeftRadians(turn);
}

public void setTurnRightRadiansOptimal(double angle) {
    double turn = normalizeRelativeAngleRadians(angle);
    if (Math.abs(turn) > HALF_PI) {
        reverseDirection();
        if (turn < 0) {
            turn = (HALF_PI + (turn % HALF_PI));
        } else if (turn > 0) {
            turn = -(HALF_PI - (turn % HALF_PI));
        }
    }
        setTurnRightRadians(turn);
}




위로


Factored Wall Avoidance 추가하기

소셜 북마크

mar.gar.in mar.gar.in
digg Digg
del.icio.us del.icio.us
Slashdot Slashdot

우리가 추가할 마지막 메소드는 adjustHeadingForWalls()이다.

이 메소드의 초반부는 벽과의 근접성에 기반하여 안전한 x,y 위치를 선택한다. (이것은 로봇의 현재 x 또는 y 좌표 또는 로봇이 벽에 가까이 있을 경우 중심점이 될 것이다.) 이 메소드의 후반부는 "안전한" 방향을 계산하고 로봇이 벽에 얼마나 근접해 있는가에 비례하여 원하는 방향으로 이를 팩토링 한다.

로봇이 벽으로 나아가는 정도는 WALL_AVOID_INTERVALWALL_AVOID_FACTORS 상수를 사용하여 조정될 수 있다.


Listing 3. 벽 피하기 메소드
                

private static final double WALL_AVOID_INTERVAL = 10;
private static final double WALL_AVOID_FACTORS = 20;
private static final double WALL_AVOID_DISTANCE =
        (WALL_AVOID_INTERVAL * WALL_AVOID_FACTORS);

private double adjustHeadingForWalls(double heading) {
    double fieldHeight = getBattleFieldHeight();
    double fieldWidth = getBattleFieldWidth();
    double centerX = (fieldWidth / 2);
    double centerY = (fieldHeight / 2);
    double currentHeading = getRelativeHeadingRadians();
    double x = getX();
    double y = getY();
    boolean nearWall = false;
    double desiredX;
    double desiredY;

    // If we are too close to a wall, calculate a course toward 
    // the center of the battlefield.
    if ((y < WALL_AVOID_DISTANCE) ||
            ((fieldHeight - y) < WALL_AVOID_DISTANCE)) {
        desiredY = centerY;
        nearWall = true;
    } else {
        desiredY = y;
    }
    if ((x < WALL_AVOID_DISTANCE) ||
            ((fieldWidth - x) < WALL_AVOID_DISTANCE)) {
        desiredX = centerX;
        nearWall = true;
    } else {
        desiredX = x;
    }

    // Determine the safe heading and factor it in with the desired 
    // heading if the bot is near a wall
    if (nearWall) {
        double desiredBearing = 
           calculateBearingToXYRadians(x, 
                                       y, 
                                       currentHeading, 
                                       desiredX, 
                                       desiredY);
        double distanceToWall = Math.min(
                Math.min(x, (fieldWidth - x)),
                Math.min(y, (fieldHeight - y)));
        int wallFactor =
                (int)Math.min((distanceToWall / WALL_AVOID_INTERVAL),
                              WALL_AVOID_FACTORS);
        return ((((WALL_AVOID_FACTORS - wallFactor) * desiredBearing) +
                 (wallFactor * heading)) / WALL_AVOID_FACTORS);
    } else {
        return heading;
    }
}




위로


결론

나머지는 쉽다. 현재의 네비게이션 알고리즘을 사용하고 adjustHeadingForWalls() 메소드를 통해 그 결과를 제공함으로써 벽을 피할 수 있다.

단순하게 하기 위해 로봇 예제(다운로드)는 방향 변경에 0을 요청하여 직선 라인으로 움직일 것이다.


Listing 4. 벽 피하기 메소드
                


public void run() {
    while(true) {
        setTurnRightRadiansOptimal(adjustHeadingForWalls(0));
        setAhead(100);
        execute();
    }
}

이제 다 되었다. 간단하지만, 효과적이다.
<출처: http://www.ibm.com/developerworks/kr/library/j-fwa/>

+ Recent posts