점화식

점화식이란?

  • 어떤 함수를 자신과 똑같은 함수를 이용해 나타내는 것

점화식의 점근적 분석 방법

  • 반복 대치 : 반복해서 집어 넣는다.

  • 추정 후 증명 : 추정 후 경계 조건 + 귀납적 가정과 전개를 이용해 증명한다. 이때 잘못 증명하지 않도록 주의해야 한다.
    • 예시  
      • 추정 : $T(n) \le 2T({n \over 2}) + n$ 의 점근적 복잡도는 $T(n) = O(nlogn)$이다. 즉, 충분히 큰 $n$에 대하여 $T(n) \le\ cnlogn$인 양의 상수 $c$가 존재한다.
      • 증명  : 
        • 경계 조건 : $T(2) \le c2log2$인 $c$가 존재  <------필수!
        • 귀납적 가정과 전개 : $ n \over 2 $에 대해 추정이 맞으면, 즉 $T({n \over 2}) \le c{n \over 2}log{n \over 2}$ 이라면 $T(n) \le 2T({n \over 2}) + n \\ \le 2c({n \over 2})log{n \over 2} + n = cnlogn - cnlog2 + n \\ = cnlogn + n(1-clog2) \le cnlogn $ $( c \ge {1 \over log2} )$
  • 마스터 정리 : $ T(n) = aT(\frac{n}{b} ) + f(n) $ 꼴을 가진 재귀식에 적용된다. 이때 $ a, b, f(n) $은 알고 있다.

실제 정의
근사 버전

 

'22-1학기 > 알고리즘' 카테고리의 다른 글

5. 검색 트리  (0) 2022.04.06
4. 선택 알고리즘  (0) 2022.04.06
3. 정렬  (0) 2022.03.22
1. 알고리즘 표기법  (0) 2022.03.14

Θ-표기법

  • 상한과 하한이 존재
  • f(n)의 최고차항이 $n^r$ 이면 계수 무시.

 

O-표기법

  • 상한만 존재
  • $\Theta$ 표기법에 속함
  • f(n)의 최고차항이 $n^r$ 이하이면 계수 무시.

 

 

 

Ω-표기법

  • 하한만 존재
  • $\Theta$ 표기법에 속함
  • f(n)의 최고차항이 $n^r$ 이상이면 계수 무시.

 

기타

  • o-표기법 (리틀 오): f(n)의 최고차항이 $n^r$ 미만이면 계수 무시
  • ω-표기법 (리틀 오메가) : f(n)의 최고차항이 $n^r$ 초과이면 계수 무시

 

 

 

 

 

'22-1학기 > 알고리즘' 카테고리의 다른 글

5. 검색 트리  (0) 2022.04.06
4. 선택 알고리즘  (0) 2022.04.06
3. 정렬  (0) 2022.03.22
2. 점화식과 알고리즘 복잡도 분석  (0) 2022.03.14

ROS2 package란?

  • ROS2 코드의 컨테이너
  • 최소 패키지 구조
    • package.xml : 패키지에 대한 메타 정보가 포함된 파일
    • CMakeLists.txt : 패키지 내에서 코드를 빌드하는 방법을 설명하는 파일
  • 보통 저장공간은 ~/dev_ws/src/패키지 로 구성함

 

실습

1. Create a package

--node-name NODE_NAME : name of the empty executable

cd ~/dev_ws/src
ros2 pkg create --build-type ament_cmake <package_name>
ros2 pkg create --build-type ament_cmake --node-name <node_name> <package_name>

 

2. Build a package

같은 workspace root에 존재하는 package들은 "colcon build"로 한 번에 빌드가 가능하다.

다른 workspace root에 존재한다면 개별적으로 빌드를 해야한다.

 

현재는 ~/dev_ws가 workspace이므로 이 경로에서 빌드를 해준다.

cd ~/dev_ws
colcon build

 

이렇게 하면 하위 경로의 패키지들은 전부 빌드가 된다. 패키지가 많다면 시간이 오래 걸릴 수 있다.

하나의 패키지만 빌드하고 싶다면 다음과 같은 명령어를 사용하면 된다.

colcon build --packages-select <package_name>

 

3. Source the setup file

새로운 패키지를 사용하고 실행시키기 위해서는 빌드한 것과 다른 터미널에서 ~/dev_ws에서 다음과 같은 명령어를 사용한다.

이 명령어는 작업 공간을 경로에 추가시켜준다.

. install/setup.bash

 

4. Use the package

아래와 같은 명령어로 패키지를 실행시킨다.

ros2 run <package_name> <node_name>

 

아래와 같은 결과가 출력된다.

 

5. Examine package contents

dev_ws/src/<package_name> 내부에서 ros2 pkg create ~ 명령어로 자동으로 생성된 파일과 폴더를 확인할 수 있다.

 

6. Customize package.xml

1단계에서 맨 마지막 명령어를 입력했을 때 패키지의 정보가 반환된 것을 볼 수 있다.

이 때 description: TODO: Package description 이라고 적힌 것을 볼 수 있다.

이 부분은 자동적으로 설정되지 않고 패키지를 릴리즈할 때 작성하면 된다.

maintainer 부분도 마찬가지다.

 

텍스트 에디터로 ~/dev_ws/src/<package_name>/package.xml을 수정해서 바꿀 수 있다.

 

예제에서는 다음과 같이 바꿨다.

<description> ~ </description> 부분과

<license> ~ </license> 부분만 변경하면 된다.

<?xml version="1.0"?>
<?xml-model
   href="http://download.ros.org/schema/package_format3.xsd"
   schematypens="http://www.w3.org/2001/XMLSchema"?>
<package format="3">
 <name>my_package</name>
 <version>0.0.0</version>
 <description>TODO: Package description</description>
 <maintainer email="user@todo.todo">user</maintainer>
 <license>TODO: License declaration</license>

 <buildtool_depend>ament_cmake</buildtool_depend>

 <test_depend>ament_lint_auto</test_depend>
 <test_depend>ament_lint_common</test_depend>

 <export>
   <build_type>ament_cmake</build_type>
 </export>
</package>

ros2 bag 이란?

  • topic에 pub된 데이터를 기록하기 위한 도구
  • 여러가지 topic에 대해 전달된 데이터를 누적하여 데이터베이스에 저장함 

 

실습

1. 설정

- 터미널 1

ros2 run turtlesim turtlesim_node

- 터미널 2

ros2 run turtlesim turtle_teleop_key

- 터미널 3 ( 저장 디렉토리 생성 및 이동 )

mkdir bag_files
cd bag_files

 

2. Choose a topic

- 터미널 3 ( topic 목록 )

ros2 topic list

 

이해를 쉽게 하기 위해서 rqt_graph를 띄워보았다.

아래에서 볼 수 있듯이 /turtle_teleop node가 거북이를 움직이게 하기 위해서 /turtle1/cmd_vel topic을  pub한다.

 

이 데이터를 보기 위해서는 다음과 같은 명령어를 사용할 수 있다. (필수는 아님 그냥 시각화)

ros2 topic echo /turtle1/cmd_vel

 

3. ros2 bag record

데이터를 기록하려면

- ros2 bag record <topic_name>

이라는 명령어를 사용한다.

 

- 터미널 3

ros2 bag record /turtle1/cmd_vel

 

터미널 2를 활성화 시킨 후 거북이를 움직인다. 

^C(Ctrc+C)를 눌러 종료한다.

 

3.1 Record multiple topics

-o 옵션을 추가하면 파일의 이름을 지정할 수 있다.

- 터미널 3

ros2 bag record -o subset /turtle1/cmd_vel /turtle1/pose

 

추가로 한 번에 여러 topic을 기록하려면 각 topic을 공백으로 구분해서 나열하면 된다.

 

-a 옵션을 추가하면 시스템의 모든 topic을 기록할 수 있다.

 

4. ros2 bag info

- ros2 bag info <bag_file_name>

이 명령어를 사용해서 세부정보를 볼 수 있다.

 

- 터미널 3

ros2 bag info subset

 

 

5. ros2 bag play

터미널 2를 Ctrl+C를 눌러 종료시킨다.

 

- 터미널 3

ros2 bag play subset

 

거북이가 앞서 움직였던 것과 비슷하게 움직이는 모습을 볼 수 있다.

rqt_console이란?

ROS2에서 log 메시지를 검사하는 데 사용되는 GUI 도구

 

실습

1. 설정

- 터미널 1

ros2 run rqt_console rqt_console

- 터미널 2

ros2 run turtlesim turtlesim_node

 

2. Messages on rqt_console

log 메시지를 만들기 위해 거북이를 벽에 부딪히게 한다.

- 터미널 3

ros2 topic pub -r 1 /turtle1/cmd_vel geometry_msgs/msg/Twist "{linear: {x: 2.0, y: 0.0, z: 0.0}, angular: {x: 0.0,y: 0.0,z: 0.0}}"

 

아래의 사진처럼 터미널의 log가 rqt_console에 출력되는 것을 볼 수 있다.

 

 

3. Logger levels

  • Fatal : 시스템이 손상되지 않기 위해 종료
  • Error : 시스템을 반드시 손상시키지는 않지만 제대로 작동하지 못하게 하는 문제
  • Warn : 기능에 해를 끼치지는 않지만 비이상적인 결과 / 심각한 문제 발생할 수 있음을 경고
  • Info : 시스템이 예상대로 실행되고 있음을 시각적으로 확인하는 역할
  • Debug : 시스템 실행의 전체 단계별 프로세스를 자세히 설명. 숨겨짐

 

3.1 Set the default logger level

아래와 같은 명령어를 사용하면 Warn 미만의 log는 출력되지 않는다.

Warn 대신에 Error를 쓰면 Warn log 메시지가 출력되지 않는다.

ros2 run turtlesim turtlesim_node --ros-args --log-level WARN

Action이란?

  • 장기 실행 작업을 위한 ros2의 통신 방법
  • topic & service 기반
  • client-server 모델 사용

 

 

실습

1. 설정

터미널 2개를 열고 다음과 같은 명령어를 실행한다.

(참고 : ros2 run <package_name> <executable_name>)

- 터미널 1

ros2 run turtlesim turtlesim_node

- 터미널 2

ros2 run turtlesim turtle_teleop_key

 

2. Use actions

터미널 2 에 명령어를 입력했을 때 G|B|V~ 라는 출력을 볼 수 있다.

이는 키보드에서 F를 둘러싼 키들인데 각각 거북이의 머리를 어디로 둘 것이냐 하는 키다.

F는 거북이가 회전하는 도중에 누르면 거북이가 회전하다가 멈춘다.

 

 

3. ros2 node info

- 터미널 3

ros2 node info /turtlesim

 

위와 같은 명령어를 치면 /turtlesim의 subscriber, publisher, service, action server, action client list가 출력된다.

/turtlesim
  Subscribers:
    /parameter_events: rcl_interfaces/msg/ParameterEvent
    /turtle1/cmd_vel: geometry_msgs/msg/Twist
  Publishers:
    /parameter_events: rcl_interfaces/msg/ParameterEvent
    /rosout: rcl_interfaces/msg/Log
    /turtle1/color_sensor: turtlesim/msg/Color
    /turtle1/pose: turtlesim/msg/Pose
  Services:
    /clear: std_srvs/srv/Empty
    /kill: turtlesim/srv/Kill
    /reset: std_srvs/srv/Empty
    /spawn: turtlesim/srv/Spawn
    /turtle1/set_pen: turtlesim/srv/SetPen
    /turtle1/teleport_absolute: turtlesim/srv/TeleportAbsolute
    /turtle1/teleport_relative: turtlesim/srv/TeleportRelative
    /turtlesim/describe_parameters: rcl_interfaces/srv/DescribeParameters
    /turtlesim/get_parameter_types: rcl_interfaces/srv/GetParameterTypes
    /turtlesim/get_parameters: rcl_interfaces/srv/GetParameters
    /turtlesim/list_parameters: rcl_interfaces/srv/ListParameters
    /turtlesim/set_parameters: rcl_interfaces/srv/SetParameters
    /turtlesim/set_parameters_atomically: rcl_interfaces/srv/SetParametersAtomically
  Action Servers:
    /turtle1/rotate_absolute: turtlesim/action/RotateAbsolute
  Action Clients:

 

여기서 /turtle1/rotate_absolute이 Action Server인 것을 알 수 있는데 이건 /turtlesim이 /turtle1/rotate_absolute action에 대해 응답하고 피드백한다는 것을 의미한다.

 

 

반대로 아래 명령어의 출력을 확인해보면

ros2 node info /teleop_turtle

Action Clients 아래에 /turtle1/rotate_absolute 가 존재하는 것을 알 수 있는데 이건 이 action에 대해 goal을 보낸다는 것을 의미한다.

 

--- 주관적 해석 ---

/teleop_turtle에서 goal을 설정해주면

/turtlesim에서 응답 및 피드백을 보내준다.

 

 

4. ros2 action list

action list를 확인하려면 다음과 같은 명령어를 사용한다.

ros2 action list

 

현재는 /turtle1/rotate_absolute 이 결과를 반환할 것이다.

 

추가적으로 다음 명령어를 사용하면 action의 type도 함께 알아낼 수 있다.

ros2 action list -t

 

현재는 /turtle1/rotate_absolute [turtlesim/action/RotateAbsolute] 을 반환한다.

 

 

 

5. ros2 action info

- 터미널 3

ros2 action info /turtle1/rotate_absolute

 

출력은 다음과 같다.

Action: /turtle1/rotate_absolute
Action clients: 1
    /teleop_turtle
Action servers: 1
    /turtlesim

 

 

6. ros2 interface show

action goal을 직접 보내거나 실행하기 위해선 구조를 알아야한다. 다음 명령어를 사용한다.

ros2 interface show turtlesim/action/RotateAbsolute

 

출력은 다음과 같다.

# The desired heading in radians
float32 theta
---
# The angular displacement in radians to the starting position
float32 delta
---
# The remaining rotation in radians
float32 remaining

 

section1 : goal request의 구조

section2 : result의 구조

section3 : feedback의 구조

더보기

예를 들어 10을 보냈는데 8만큼 돌았다고 가정해보자.

goal request : 10

result : 8

feedback : 2

 

7. ros2 action send_goal

action goal을 터미널에서 실행하는 명령어는 다음과 같다.

ros2 action send_goal <action_name> <action_type> <values>

 

- 터미널 3

ros2 action send_goal /turtle1/rotate_absolute turtlesim/action/RotateAbsolute "{theta: 1.57}"

 

다음과 같은 결과가 반환된다.

Waiting for an action server to become available...
Sending goal:
     theta: 1.57

Goal accepted with ID: 87cff62b6d97438b87d5433048a3ba34

Result:
    delta: 0.0

Goal finished with status: SUCCEEDED

 

 

여기에 피드백을 추가하려면 feedback 옵션을 추가한다.

ros2 action send_goal /turtle1/rotate_absolute turtlesim/action/RotateAbsolute "{theta: -1.57}" --feedback

 

목표가 완료될 때까지 피드백을 계속해서 받는다.

parameter란?

  • node의 구성 값 ( = node 설정 )
  • int, float, bool, string, list로 저장 가능'

 

실습

1. 설정

터미널 2개를 열고 다음과 같은 명령어를 실행한다.

(참고 : ros2 run <package_name> <executable_name>)

- 터미널 1

ros2 run turtlesim turtlesim_node

- 터미널 2

ros2 run turtlesim turtle_teleop_key

 

2. ros2 param list

node에 속한 parameter를 보려면 다음과 같은 명령어를 입력한다.

- 터미널 3

ros2 param list

 

아래와 같이 출력된다.

/teleop_turtle:
  scale_angular
  scale_linear
  use_sim_time
/turtlesim:
  background_b
  background_g
  background_r
  use_sim_time

 

 

3. ros2 param get

매개변수 값을 확인하기 위해선 아래와 같은 명령어를 사용한다.

ros2 param get <node_name> <parameter_name>

 

예를 들어 다음과 같이 명령어를 실행해서 배경의 rgb 중 g 값을 알아낼 수 있다.

- 터미널 3

ros2 param get /turtlesim background_g

 

 

4. ros2 param set

런타임 시에 매개변수 값을 변경하려면 다음 명령을 사용한다.

ros2 param set <node_name> <parameter_name> <value>

 

/turtlesim의 배경색을 변경하기 위해선 아래와 같은 명령어를 사용하면 된다.

ros2 param set /turtlesim background_r 150

아래 사진처럼 배경색이 바뀐다.

 

이 명령은 영구적으로 저장되지 않고 현재 세션에만 저장된다.

 

 

5. ros2 param dump

file로 변경한 명령을 저장할 수 있는 명령어이다.

ros2 param dump <node_name>

 

아까 바꿨던 설정을 저장하기 위해선 아래와 같은 명령어를 사용한다.

ros2 param dump /turtlesim

 

./turtlesim.yaml에서 변경된 값을 확인할 수 있다.

 

 

6. ros2 param load

방금 저장한 파일을 이용해서 파라미터를 변경한다.

ros2 param load <node_name> <parameter_file>

 

- 터미널 3

ros2 param set /turtlesim background_r 0
ros2 param load /turtlesim ./turtlesim.yaml

 

결과는 아래와 같다.

 

 

7. Load parameter file on node startup

저장한 파라미터로 동일한 노드를 실행하려면 다음과 같은 명령어를 사용한다.

ros2 run <package_name> <executable_name> --ros-args --params-file <file_name>

 

- 터미널 3

ros2 run turtlesim turtlesim_node --ros-args --params-file ./turtlesim.yaml

 

service란?

  • topic 이외의 노드 간 통신 방법
  • topic을 통해 node는 데이터 스트림을 구독해 지속적인 업데이트를 얻을 수 있지만 service는 client가 특별히 호출한 경우에만 데이터를 요청

 

실습

1. 설정

- 터미널 1

ros2 run turtlesim turtlesim_node

- 터미널 2

ros2 run turtlesim turtle_teleop_key

 

2. ros2 service list

현재 활성화 된 service list 확인 명령어는 아래와 같다.

- 터미널 3

ros2 service list

아래와 같이 출력된다.

/clear
/kill
/reset
/spawn
/teleop_turtle/describe_parameters
/teleop_turtle/get_parameter_types
/teleop_turtle/get_parameters
/teleop_turtle/list_parameters
/teleop_turtle/set_parameters
/teleop_turtle/set_parameters_atomically
/turtle1/set_pen
/turtle1/teleport_absolute
/turtle1/teleport_relative
/turtlesim/describe_parameters
/turtlesim/get_parameter_types
/turtlesim/get_parameters
/turtlesim/list_parameters
/turtlesim/set_parameters
/turtlesim/set_parameters_atomically

 

3. ros2 service type

service type은 topic과 비슷하게 정의되지만 요청과 응답 두 부분이 존재한다.

 

service type은 다음 명령으로 찾을 수 있다.

- 특정 service 확인

ros2 service type <service_name>

ex) ros2 service type /clear

 

- 전체 service 확인

ros2 service list -t

 

 

4. ros2 service find

특정 타입을 사용하는 서비스를 찾고 싶다면, 다음과 같은 명령어를 사용하면 된다.

ros2 service find <type_name>

예를 들어 std_srvs/srv/Empty 형식을 사용하는 서비스를 찾고 싶다면 아래와 같은 명령어를 입력한다.

- 터미널 3

ros2 service find std_srvs/srv/Empty

그러면 다음과 같이 출력된다.

 

 

5. ros2 interface show

topic 예제에서 했던 것처럼 service type을 구체적으로 확인해보자.

 

-터미널3 (ros2 interface show <type_name>.srv)

ros2 interface show turtlesim/srv/Spawn.srv

아래와 같이 출력된다.

 

--- 위의 4줄은 /spawn을 호출하려면 필요한 인자들을 말한다. 

이 경우는 아니지만 보통 --- 라인 아래는 호출에서 받은 응답의 데이터 유형을 이해하는 데 도움이 된다.

 

 

6. ros2 service call

ros2 service call <service_name> <service_type> <arguments>

위와 같은 명령어를 이용해서 터미널에서도 서비스를 호출할 수 있다.

 

- ros2 interface show std_srvs/srv/Empty.srv

이 명령어를 통해서 이 서비스에는 인자가 없다는 것을 알 수 있다.

따라서 다음과 같은 명령어를 사용하면 거북이가 그린 선을 모두 지울 수 있다.

ros2 service call /clear std_srvs/srv/Empty

 

또한 아래의 명령어를 이용해서 새로운 거북이를 만들 수 있다.

ros2 service call /spawn turtlesim/srv/Spawn "{x: 2, y: 2, theta: 0.2, name: ''}"

 

+ Recent posts